平面最近点对 | Codeboy's Blog

形式陈述

这是计算几何中的基本问题：固定实平面的标准 Euclidean 内积，输入是 $n\ge2$ 个平面点，输出欧氏距离最小的一对及距离。两点 $(x_1,y_1),(x_2,y_2)$ 的距离为 $\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$ ；比较距离时可以比较平方值，避免每次开方。先按 $(x,y)$ 字典序排序，相同坐标仍保留各自的输入身份，递归求分割线左右最近距离 $\delta_L,\delta_R$ ，令 $\delta=\min(\delta_L,\delta_R)$ 。任何更短的跨侧点对都必须同时位于距分割线小于 $\delta$ 的竖直 strip 中。

递归的接口还要返回本子问题中按 $y$ 排序的点列；父调用用双路归并合并两个有序列，再以线性时间筛出 strip。至多三个点的子问题直接比较所有点对，并排好返回点列。先排除重复点，使 $\delta>0$ 。对带中一点 $p$ ，只有纵坐标位于 $[p_y,p_y+\delta)$ 的后继可能与它形成更短点对。将这个宽 $2\delta$ 、高 $\delta$ 的矩形按左右递归归属分成两个 $\delta\times\delta$ 方块，再把每块分成四个边长 $\delta/2$ 的半开小格。同侧每格至多一点，因为格内两点距离至多 $\delta/\sqrt2<\delta$ ，会违反该侧递归答案。八格合计至多八点，其中已有 $p$ ，所以只需检查按 $y$ 排序的后续至多七点。分割线上的点按原排序位置保留左右身份；不能因坐标相同把两侧的分离条件混在一起。故

T(n)=T(\lfloor n/2\rfloor)+T(\lceil n/2\rceil)+O(n)=O(n\log n),

在坐标比较、加乘与距离比较均为常数成本的实数 RAM 模型下，额外空间可做到 $O(n)$ ；任意精度坐标还需计入数值运算成本。若每层重新按 $y$ 排序，合并成本变成 $O(n\log n)$ ，总时间退化为 $O(n\log^2 n)$ 。

直觉

分治先排除左右内部的大多数点对，只留下可能跨越分割线的窄带。Packing 不是经验猜测，而是数量证书：已知同侧点不能靠得比 $\delta$ 更近后，一个局部矩形中能挤入的候选数受常数限制。

全局有平方多个点对，算法却只在每层检查线性多个局部候选；真正的加速来自几何分离，而非单纯把点数组切成两半。

图中的竖直带筛选横向距离，按纵坐标排列则筛选纵向距离；只有同时通过两次筛选的点对才需要计算完整距离。

例子与边界

取左侧点 $A=(-2,0),B=(-0.1,2)$ ，右侧点 $C=(0.1,2.1),D=(2,0)$ ，以 $x=0$ 分割。左、右内部距离分别为 $\sqrt{7.61}$ 和 $\sqrt{8.02}$ ，故初始 $\delta=\sqrt{7.61}$ 。但跨侧 $BC$ 的距离只有 $\sqrt{0.05}$ ，只取两个递归答案会漏掉真正最优对。

合并后的 $y$ 次序为 $A,D,B,C$ （相同 $y$ 的顺序任选）。四点都在初始窄带内，扫描到 $B$ 时，其后继 $C$ 的纵向差为 $0.1<\delta$ ，因而比较并把答案降为 $\sqrt{0.05}$ 。窄带之所以足够，是因为跨侧两点的横向距离至少等于任何一端到分割线的距离；距分割线已达 $\delta$ 的点不可能参与更短答案。

输入含重复点时答案立即为零，排序阶段即可检测；继续套 packing 证明会违反“同侧点至少相距 $\delta>0$ ”的前提。多个点共享 $x$ 坐标时，划分应按排序位置平衡，并保持点身份，不能仅用 $x<x_{\mathrm{mid}}$ 导致一侧空或重复归属。

“检查七个后继”依赖具体 strip 宽度、边界归属和分格证明；换一种闭区间约定可能得到另一个常数，但不改变线性合并。实现应证明自己的常数覆盖所有候选，而不是把数字当作魔法循环上界。

推论与应用

最近点对是几何分治的典型闭环：预排序、递归不变量、合并证书和复杂度递推缺一不可。它用于碰撞预筛、聚类和空间数据分析，也为 Delaunay 邻接包含最近点对提供直觉。

高维 packing 常数随维数快速增长，算法虽可推广却不再有同样工程优势。不同度量下 strip 形状和局部装填界也会改变，不能直接复用 Euclidean 的七邻居实现。

参考资料

Robert Sedgewick、Kevin Wayne，Algorithms 配套代码，ClosestPair.java，在线版，访问于2026年：closest 的按位置划分、按 $y$ 归并与窄带扫描。
Michael I. Shamos and Dan Hoey, “Closest-Point Problems,” FOCS 1975, pp. 151–162.
Thomas H. Cormen et al., Introduction to Algorithms, 3rd ed., MIT Press, 2009, §33.4.

形式陈述 ​

反向链接

形式陈述