2.3 最近点对算法

前面两篇的分治都用在"数"上（排序、选择）。这一篇我们把它带到几何世界——平面上 $n$ 个点，找距离最近的那一对。朴素做法是两两算距离， $O(n^2)$ ；但分治能把它压到 $O(n\log n)$ 。你会看到，分治这套"切两半"的结构，在几何问题上照样work，而且又冒出一个分治的标志性细节——"跨边界的情况怎么处理"。

1.问题与朴素解法

平面上 $n$ 个点 $p_1,\dots,p_n$ ，找 $\min_{i\ne j}\text{dist}(p_i,p_j)$ （两点欧氏距离的最小值）。朴素地枚举所有 $\binom{n}{2}$ 对，每对算一次距离， $O(n^2)$ 。 $n$ 一万就一亿次，吃不消。

我们要做到 $O(n\log n)$ 。

2.分治：先分，跨边界再小心

按惯例，把点集对半切。但切法有讲究：按 x 坐标排个序，从中间竖着切一刀，分成左半 $L$ 和右半 $R$ 。

最短距离只有三种来源：
  ① 两点都在左半 → 递归左半求得 dL
  ② 两点都在右半 → 递归右半求得 dR
  ③ 一点在左一点在右（跨边界）→ 需要单独处理

令 $d=\min(d_L, d_R)$ 。前两种情况递归就解决了。难的是③——跨边界的那对点，距离可能小于 $d$ ，是朴素法会漏的。

这里有个分治几何题的经典技巧，叫做**"跨越分界线的点对，距离若小于 $d$ ，只可能出现在分界线两侧各宽 $d$ 的窄条里"**。这不难理解：离分界线超过 $d$ 的点，光横跨距离就超过 $d$ 了，不可能是答案。

        分界线 L
    ←——d——|——d——→
   左窄条   |   右窄条
           |
  收集窄条里的点，按 y 排序

更妙的是，对窄条里任意一个点，能和它配对的（距离 $<d$ 的）候选点，在 $y$ 方向上最多只有常数个（最多 6 或 7 个，因为它们都得落在 $2d\times d$ 的矩形里，而这矩形里塞不下超过 8 个相距 $\ge d$ 的点）。所以窄条里的点按 $y$ 排序后，每个点只需和后面常数个点比，窄条总代价 $O(n)$ 。

3.完整算法

CLOSEST-PAIR(P)
    按 x 排序得到 Px，按 y 排序得到 Py
    return CLOSEST-PAIR-REC(Px, Py)

CLOSEST-PAIR-REC(Px, Py)
    if n <= 3: 直接算（暴力）          // 基底
    沿 x 中线切，得左半 Lx、右半 Rx
    从 Py 里分出左 Ly、右 Ry（按 y 已排好序）
    dL = CLOSEST-PAIR-REC(Lx, Ly)
    dR = CLOSEST-PAIR-REC(Rx, Ry)
    d = min(dL, dR)
    // 收集 Py 里离中线 < d 的点，得到窄条 Y'
    d_cross = 处理窄条 Y'：对每个点，和后面最多 7 个点比距离
    return min(d, d_cross)

注意 Py 这个按 $y$ 预排序的数组贯穿递归传递，避免了每层重新排序——这是把复杂度从 $O(n\log^2 n)$ 压到 $O(n\log n)$ 的关键细节。

4.复杂度： $T(n)=2T(n/2)+O(n)=O(n\log n)$

递归两边各 $n/2$ ，合并（窄条处理） $O(n)$ 。 $T(n)=2T(n/2)+O(n)=\Theta(n\log n)$ ——和归并排序一模一样的递归关系，一模一样的解。

这里值得再品味那个"窄条里每个点只需比常数个点"的事实。它为什么成立？因为左右两半各自内部的最短距离都 $\ge d$ ，所以窄条这个 $2d\times d$ 的矩形区域里，无论左侧还是右侧，相邻点（按 $y$ ）的距离都 $\ge d$ 。一个 $2d\times d$ 的矩形，每侧最多塞下 4 个两两距离 $\ge d$ 的点（鸽巢），两侧共最多 8 个。所以固定一个点，对面侧能与它距离 $<d$ 的点不超过 4 个，加上同侧按 $y$ 邻近的，常数级别。这个"常数"是整个算法线性的命门——它让窄条处理不退化成 $O(n^2)$ 。

5.分治几何题的通用范式

最近点对几乎是所有"分治 + 跨边界处理"几何题的模板。它的范式你可以记下来，将来碰到类似题往里套：

选一个维度排序，按中位数切两半。
递归求两半各自的最优。
合并：考虑跨越分界线的情况，用一个"窄带/缓冲区"把候选点限制在常数规模。
缓冲区内按另一维度排序，每个点只查常数个邻居。

第 3、4 步是这个范式的精髓——把"无限多的跨边界对"压缩成"常数多的候选对"，靠的是一个鸽巢/几何 packing 论证。下一篇凸包也会用到类似的几何 packing 思想。

6.练习

Q1. 为什么处理跨边界点对时，只看离中线小于 $d$ 的窄条就够了？

因为若某点离中线 $\ge d$ ，它和对面任意点的水平距离就 $\ge d$ ，总距离必 $\ge d$ ，不可能是比 $d$ 更短的答案。所以只有落在中线两侧各宽 $d$ 的窄条里的点，才可能配出 $<d$ 的跨边界对。这一步把候选从"所有跨边界对"压缩到"窄条里的点对"。

Q2. 为什么窄条里按 $y$ 排序后，每个点只需和后面最多 7 个点比距离？

因为左右半各自内部最短距离 $\ge d$ ，窄带这个 $2d\times d$ 矩形里，每侧最多塞 4 个两两距离 $\ge d$ 的点（鸽巢），两侧共最多 8 个。固定一个点，对面侧能与它距离 $<d$ 的点 $\le 4$ 个，加上同侧邻近的常数个，总共 $O(1)$ 个。这个常数保证是窄带处理线性的命门。

Q3.（思考题） 为什么要把 Py（按 y 预排序的数组）贯穿递归传递，而不是每层重新排序？

若每层重新按 $y$ 排序，合并代价变成 $O(n\log n)$ ，总复杂度 $T(n)=2T(n/2)+O(n\log n)=O(n\log^2 n)$ ，多一个 $\log$ 。预先排好 Py 并在递归里按"属于左/右"线性拆分传递，合并就能保持 $O(n)$ ，总复杂度回到 $O(n\log n)$ 。这是"预排序省一个 $\log$ "的经典技巧。

7.小结

最近点对用分治把 $O(n^2)$ 压到 $O(n\log n)$ ：按 $x$ 切两半递归，跨边界情况用一个 $d$ 宽窄条 + 鸽巢论证压缩成常数候选。它确立了"分治 + 跨边界缓冲区"的几何范式。下一篇我们继续在几何里，用分治求凸包。