平面最近点对问题：如何用分治在 O(n log n) 时间求最近的两点？

简化版

给平面上 n 个点，求距离最近的两点。暴力枚举所有点对是 O(n²)。分治：按 x 坐标把点从中线切成左右两半，递归求出左半最小距离 d1、右半最小距离 d2，取 d=min(d1,d2)；再处理跨中线的点对——只有横坐标离中线小于 d 的「窄带（strip）」里的点才可能更近，把它们按 y 排序后，每个点只需和后面至多 6~7 个点比较（几何可证）。合并 O(n)，递归式 T(n)=2T(n/2)+O(n) → O(n log n)。

详细版

算法框架：

预排序：把点按 x 坐标排好（一次即可）。
分：用竖直中线 x = mid_x 把点分成左右两半。
治：递归求左半最小距离 d1、右半最小距离 d2，令 d = min(d1, d2)。
合（难点）：最近点对可能一个在左、一个在右（跨中线）。只有满足 |x − mid_x| < d 的点组成的窄带里才可能出现更近的对。把窄带内的点按 y 升序排列，对每个点，只与其后 y 差小于 d 的点比较——几何证明这样的点至多 7 个（常数个），逐一更新 d。

复杂度：

每层递归 O(n) 合并，T(n) = 2T(n/2) + O(n) → O(n log n)；
但窄带内每层都按 y 重新排序会变成 O(n log n) 每层、总 O(n log² n)；把 y 排序像归并那样沿递归自底向上维护，每层降到 O(n)，才是严格的 O(n log n)。

完整版教学

一、暴力 O(n²) 与分治动机

「最近点对」：平面上 n 个点，找出欧几里得距离最小的那一对。最直接是双重循环枚举所有 C(n,2) 对，算距离取最小，O(n²)。点一多就吃力。这是计算几何里用分治把 O(n²) 降到 O(n log n) 的经典范例，思路和「归并」一脉相承。

二、分治框架：按 x 中线切分

分：把所有点按 x 坐标排序，取中位数处画一条竖直中线，分成左半、右半各约 n/2 个点。
治：递归地在左半求最近距离 d1、右半求 d2。递归到只剩 2~3 个点时直接暴力算（递归基）。
令 d = min(d1, d2)——这是**「两个端点在同一半」** 的最优解。

但还差一种情况没考虑：最近的两点可能分居中线两侧。这就是合并步要解决的难点。

三、难点：跨中线的点对（窄带 strip）

跨中线的点对，如果比 d 还近，那这两个点离中线都不会太远——横坐标与中线的距离必然都小于 d（否则两点横向就已经拉开超过 d，不可能更近）。

于是只需考察「窄带」：所有满足 |x − mid_x| < d 的点。看起来窄带里可能有很多点、两两比较又回到 O(n²)？关键的几何性质救场：把窄带内的点按 y 坐标排序后，任意一个点，只需要和排在它后面的常数个点比较即可。这样窄带处理是 O(n)，不会拖垮复杂度。

四、为什么窄带内每点只比较常数个点（几何证明）

考虑窄带里某个点 p。任何能和 p 构成「更近对」的点 q，必须满足 |y_p − y_q| < d（y 方向也不能差太多）。所以候选点都落在一个 宽 2d（中线左右各 d）、高 d 的矩形里，且 p 在矩形底边。

把这个矩形按中线分成左右两个 d × d 的方格。同一个方格内，任意两点的距离都 < d（方格对角线 = d√2……实际上要用「同一半内部最近距离已 ≥ d」这一事实）：由于左半内部两点距离 ≥ d1 ≥ d、右半内部两点距离 ≥ d2 ≥ d，所以每个 d × d 方格里最多容纳 4 个点（再多必有两点距离 < d，矛盾）。两个方格合起来至多 8 个点，去掉 p 自己，p 至多和 7 个点比较。

这个「至多 7 个」（更精细的分析能收紧到 6 个甚至更少）是把窄带处理压到 O(n) 的关键——它把「窄带内两两比较」从 O(n²) 变成「每点 × 常数」。

五、复杂度：预排序避免每层重排

朴素实现里，窄带处理要「按 y 排序」，若每层递归都排一次序，每层就是 O(n log n)，总 T(n)=2T(n/2)+O(n log n)=O(n log² n)。
优化：像归并排序一样，在递归返回时顺带把子问题的点按 y 归并成有序，父问题直接拿到 y 有序的序列，窄带处理只需 O(n) 扫描。这样每层 O(n)，T(n)=2T(n/2)+O(n)=O(n log n)。
x 方向的排序只在最开始做一次（O(n log n)），不在递归里重复。

所以严格的 O(n log n) 实现 = 「x 预排序一次 + 递归中用归并维护 y 有序」。面试能讲清 O(n log² n) 和 O(n log n) 的差别是加分点。

六、递归式、合并证明与数字推演

这道题的分治闭环是：左右递归已给出距离 δ，跨中线候选只需保留横向距离小于 δ 的窄带，并按 y 顺序比较常数个后继。递归调用只保证子问题正确，原问题能否正确仍取决于合并步骤是否覆盖所有情况且不重不漏。

T(n)=2T(n/2)+Θ(n)=Θ(n log n)，前提是 y 序在递归中线性维护
递归树核对：每层子问题数 × 单个子问题的非递归代价

带数字推演：δ=5 时只保留 x 距中线小于 5 的点；在 5×10 的局部矩形中打包论证限制邻点数量。推演时应记录每层输入规模、进入哪些子问题、合并新增了什么信息，不能只写最终答案。

记忆钩子：先写“分成什么、递归返回什么、怎样合并”，再列递推式；只会套主定理而说不清合并，说明算法还没有真正掌握。

七、实现代价、退化条件与替代方案

实现边界是：若每层重新按 y 排序会变为 O(n log²n)；距离平方可避免浮点开方，坐标差平方要防溢出。除了渐进时间，还要把递归栈、辅助数组、输入是否被修改以及最坏输入考虑进去。

检查项	面试中要回答的内容
基本情况	规模 0 或 1 时如何直接返回
规模缩小	每次递归是否严格靠近基本情况
合并正确性	子解怎样推出原问题答案
资源代价	递归深度、辅助结构与数据复制
退化保护	随机化、阈值切换、预排序或迭代改写

测试至少覆盖最小规模、奇偶长度、全部相等、严格有序/逆序、极端偏斜划分和会触发最大计数或溢出的数据。若存在更直接的线性算法、堆算法或动态规划，还要说明分治方案的教学价值与工程取舍。

“每点只比较常数个后继”来自平面装箱论证，而不是经验规则。把窄带按 δ/2 划成小方格，同一方格不能容纳两个来自同一侧且距离仍不小于 δ 的点；因此按 y 排序后，落在当前点上方 δ 高度内的候选数量有常数上界。实现中常直接检查后续至多 7 个点，但这个常数依赖二维欧氏距离的证明，不能原样推广到任意维度和距离度量。

按 y 排序的窄带候选：
p0 → 只检查 y 差 < δ 的 p1 ... p7
y 差一旦达到 δ → 后续点全部停止比较

这里的停止条件比“固定写死比较 7 次”更重要：先用 y 差剪掉必不可能更近的点，再由几何证明保证实际检查次数为常数。这样代码既忠于证明，也能处理窄带点数不足 8 的边界。

八、常见误区与追问

误区：跨中线仍需比较窄带内所有点对。 几何打包性质使每点只需检查按 y 排序后的常数个邻点。
误区：先按 x 排序后每层再按 y 排序没影响。 每层排序会多一个 log n 因子。
误区：只比较左右两半内部即可。 最近点对可能一边一个，必须处理跨中线候选。
追问：为什么用距离平方？ 比较平方与比较距离等价，并减少浮点误差和开方成本。
追问：重复点怎么办？ 距离直接为 0，可提前结束。
追问：高维还能保持相同常数吗？ 维数升高会削弱打包界，算法与常数都需重新分析。

九、加强记忆

平面最近点对分治：按 x 中线切两半，递归得左右最小距离取 d=min(d1,d2)；再查跨中线的点对——只有横坐标离中线 < d 的窄带才可能更近，窄带内按 y 排序后每点只比后面至多 7 个点（因每个 d×d 方格最多 4 点的几何性质）。合并 O(n)、T(n)=2T(n/2)+O(n) → O(n log n)（需沿递归归并维护 y 有序；否则每层重排会退化到 O(n log² n)）。

简化版

详细版