平面最近点对

形式陈述 ​

输入是 $n\ge 2$ 个平面点，输出 Euclidean 距离最小的一对及距离。先按 $x$ 坐标排序公理库比较排序Comparison sorting仅通过元素两两比较确定排列次序的排序模型。，递归求分割线左右最近距离 ${\delta }_L,{\delta }_R$，令 $\delta =min({\delta }_L,{\delta }_R)$。任何更短的跨侧点对都必须同时位于距分割线小于 $\delta$ 的竖直 strip 中。

递归过程同时维护按 $y$ 排序的点列，以线性时间筛出 strip。按标准半开分格论证，strip 中每个点只需与其后至多常数个点比较；常见实现检查后续最多七点。因为每一侧内部任意两点距离至少为 $\delta$，面积有限的小矩形无法容纳更多互相分离的候选。故

$$T(n)=2T(n/2)+O(n)=O(n\log n),$$

额外空间可做到 $O(n)$。若每层重新按 $y$ 排序，合并成本变成 $O(n\log n)$，总时间退化为 $O(n{\log }^{2}n)$。

直觉 ​

分治公理库分治法Divide and conquer把问题分成较小同类子问题，递归求解后合并结果的算法设计范式。先排除左右内部的大多数点对，只留下可能跨越分割线的窄带。Packing 不是经验猜测，而是数量证书：已知同侧点不能靠得比 $\delta$ 更近后，一个局部矩形中能挤入的候选数受常数限制。

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

例子与边界 ​

两簇点分别位于分割线左右时，各簇内部最近距离可能较大，而最优对恰由靠近分割线的两个点组成。递归答案本身会漏掉这对，strip 合并阶段正是为捕获跨侧候选；远离分割线至少 $\delta$ 的点不可能参与更优跨侧对。

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

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

推论与应用 ​

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

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

参考资料

• 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.