最近点对（分治）
计算几何 · 分治 + δ 带合并 · O(n log n)
离得最近的两个点
平面上 n 个点，找距离最近的两个——与最远点对正好对偶。暴力比较所有点对是 O(n²)；但「最近」没有「必在凸包上」这样的免费午餐（最近的点往往藏在内部），需要另一件武器：分治。
分而治之 + δ 带
把点按 x 排序，沿中线切成左右两半，各自递归求最近距离，取 δ = min(左, 右)。麻烦在合并：最近的一对可能一只脚在左、一只脚在右。但注意——这样的点对两端都必须离中线不到 δ，所以只需检查中线两侧 δ 宽的带。更妙的是把带内的点按 y 排序后，每个点只需和 y 差小于 δ 的邻居比较：一个 δ×2δ 的矩形里最多塞得下 8 个相距 ≥δ 的点（鸽笼原理），所以每点只比常数次。合并 O(n)，整体 T(n) = 2T(n/2) + O(n) = O(n log n)。
下面固定 8 个点。点「下一步」逐步看：紫色虚线是分治中线、左右两半各自求出最近对（绿线）定出 δ，然后浅紫色带亮起——带内按 y 序逐对比较（蓝色虚线），本例连刷两次：先 1.581、再 1.118——最终答案恰好跨越中线，正是 δ 带存在的意义。右侧代码随每一步同步高亮。
平面上 8 个点（已按 x 排序），找距离最近的两个。暴力 O(n²)，分治能到 O(n log n)
1function closest(pts: Pt[]): number { // pts 已按 x 排序
2 if (pts.length <= 3) return brute(pts);
3 const mid = pts.length >> 1;
4 const midX = (pts[mid - 1].x + pts[mid].x) / 2; // 中线
5 const dl = closest(pts.slice(0, mid)); // 左半递归
6 const dr = closest(pts.slice(mid)); // 右半递归
7 let d = Math.min(dl, dr); // δ
8 const strip = pts.filter(p => Math.abs(p.x - midX) < d)
9 .sort((a, b) => a.y - b.y); // δ 带内按 y 排序
10 for (let i = 0; i < strip.length; i++)
11 for (let j = i + 1; j < strip.length &&
12 strip[j].y - strip[i].y < d; j++) // 只比 y 差 < δ 的近邻
13 d = Math.min(d, dist(strip[i], strip[j])); // 跨带可能刷新
14 return d;
15}
点数8
当前最近-
1 / 10
为什么合并只要 O(n)
分治：中线分半，δ = min(左最近, 右最近)。
δ 带：跨线的更近对两端必落在 |x − 中线| < δ 的带内。
鸽笼：带内按 y 排序，每点只需比 y 差 < δ 的至多 7 个邻居。
复杂度：T(n) = 2T(n/2) + O(n) =
δ 带：跨线的更近对两端必落在 |x − 中线| < δ 的带内。
鸽笼：带内按 y 排序，每点只需比 y 差 < δ 的至多 7 个邻居。
复杂度：T(n) = 2T(n/2) + O(n) =
O(n log n)。 最近点对是「分治 + 有序合并」在几何上的招牌应用，同一套思想还支撑着归并排序、逆序对计数、平面最近异色点对等问题。它也提醒我们：分治的难点常常不在「分」，而在合并时如何不漏掉跨越边界的答案——δ 带就是那个精确的补网。