的几何算法)
最近点对问题Closest Pair of Points是我当年学算法时印象最深的一道题平面上给一堆点找出距离最近的两个点。暴力解法分分钟想到但数据量一上去就卡死。分治法的处理思路极其经典配合画图理解后整个证明和实现都会变得异常清晰。这篇文章我不仅会把分治法讲透还会用一套具体数据把每一步的图都画出来包括划分、递归、合并、候选区域这些关键环节看完你就能完整复现整个算法。1. 最近点对问题从暴力到分治的演进1.1 问题定义平面上找距离最近的两个点题目本身不复杂。假设平面上有 n 个点每个点用坐标 (x, y) 表示要求找出欧几里得距离最近的一对点。注意是点到点之间的直线距离d sqrt((x1-x2)² (y1-y2)²)这个问题的应用场景比我最初想的多。比如地理位置聚类里要找出距离最近的两个基站碰撞检测里要找出空间中距离最近的两个对象还有图像处理中的特征点匹配第一步往往都是找最近邻居。很多更大规模的问题会把最近点对当作一个子过程反复调用所以这个基础算法能不能跑得快直接影响整个系统的性能。我刚学的时候第一反应就是暴力法把所有点两两组合都算一遍距离记录最小值。两层循环搞定代码简单到不用思考。但问题在于复杂度。n 个点两两组合有 C(n,2) n(n-1)/2 种情况时间复杂度是 O(n²)。n 等于 1000 的时候大约要算 50 万次距离n 等于 10 万的时候就是 50 亿次。这个增长趋势会迅速击穿计算资源。实际项目中如果点集规模上了万O(n²) 的暴力解法基本就是不可用的必须找更聪明的办法。1.2 为什么暴力解会卡死规模增长的速度我拿一组实际数据感受一下。假设一秒钟能算 1000 万次距离已经是相当乐观的估算不同规模的点集会呈现这样的耗时点数量 n两两组合数量估算耗时1,000约 50 万0.05 秒10,000约 5000 万5 秒100,000约 50 亿500 秒1,000,000约 5000 亿50000 秒n 从 1 千涨到 100 万点数量只多了 1000 倍耗时却多了约 100 万倍。这就是 O(n²) 的可怕之处。而且这还只是距离计算还没算上距离比较、临时变量维护这些开销。真实场景里点动辄几十万个暴力法基本不可行。所以问题的关键变成了能不能把复杂度压到 O(n log n) 甚至 O(n)分治法正好能做到 O(n log n)而且思路非常符合直觉就是大事化小、小事化了。2. 分治法的整体设计与画图拆解2.1 三步走划分、递归、合并分治法处理最近点对的标准流程可以总结成三步。第一步划分。把所有点按照 x 坐标排序然后取中位数用一条垂直于 x 轴的线把点集分成左半和右半两部分两边点数尽量均衡。第二步递归。分别对左半部分和右半部分递归地求解最近点对得到左半内部的最近距离 dL 和右半内部的最近距离 dR。递归出口是区间里只有一个点或两个点一个点没有距离直接返回无穷大两个点直接算它们之间的距离。第三步合并。这是最关键的步骤。全局最近点对除了可能出现在左半内部或右半内部还有一种特殊情况一个点在左半一个点在右半它们跨越了分割线。这类跨线点对需要在合并时专门处理。合并的目标就是找出所有跨线点对中的最近距离然后跟 dL、dR 比较取最小值。这个三步走看起来平淡无奇但合并步骤里藏着一个几乎所有初学者都会忽略的优化点跨线点对到底要检查哪些点如果无脑把所有左半点和所有右半点两两比较那复杂度又回到 O(n²)分治就白做了。2.2 用一张图画清分治过程理解分治最好的方式就是画图。我用一组具体数据演示点集一共 8 个点随便编一组坐标但特意设计成跨线点对会成为最终答案这样合并步骤的意义才能体现出来。点集分布示意 y 31 L3 30 L1 28 L2 ... 16 R3 15 R1 13 R2 8 6 4 B 3 L4 ----------------------------------------------------------- x 1 2 3 4 5 6 7 8 9 ... 20 21 228 个点按 x 坐标排序后是编号坐标左/右半区L1(1, 30)左半L2(2, 28)左半L3(3, 31)左半L4(5, 3)左半B(6, 4)右半R1(20, 15)右半R2(21, 13)右半R3(22, 16)右半初始状态按 x 坐标排序后取中间位置把点集切成左右各 4 个。分割线画在 x 5.5 左右也就是 L4 和 B 之间。分割示意 y 31 L3 30 L1 28 L2 ... 16 R3 15 R1 13 R2 4 B 3 L4 |← 左半4个点 →|← 右半4个点 →| x5.5后面整个算法的推演我都会基于这张图来讲。你看到的是先竖着切一刀左右各自找最短再检查跨线区域这套逻辑配上图就完全不会乱。3. 合并步骤真正的大 Boss3.1 strip 区域哪些点值得检查合并时的朴素做法是把左半所有点和右半所有点都两两算一遍。但这显然不行。仔细想想就会发现大部分跨线点对根本不可能成为最优解。已知当前最佳的左右内部距离是 d min(dL, dR)。如果跨线点对的距离要小于 d那么这两个点的 x 坐标都不能离分割线太远。具体来说任何一个点如果它的 x 坐标与分割线的水平距离已经大于等于 d那它跟对面任何一个点的距离都不可能小于 d。因为欧几里得距离必然大于等于水平方向的差距。所以真正值得检查的候选区域是以分割线为中心、宽度为 2d 的一条竖直带状区域通常叫 strip。分割线左边 d 宽右边 d 宽。strip 区域示意 y 31 L3 30 L1 28 L2 ... 16 R3 15 R1 13 R2 4 B 3 L4 | | | |← d →| | strip左边界 分割线 strip右边界 x5.5-d x5.5 x5.5dstrip 区域之外的点直接忽略因为它们在水平方向上就不够格。这个剪枝让候选点数量大幅减少。但问题还没完全解决如果点分布很密strip 里可能依然有大量点全两两比较还是灾难。3.2 在 strip 内按 y 坐标排序滑动窗口的思想strip 内的点不能继续用 x 方向来剪枝了因为它们 x 方向都在分割线附近。这里换一个思路把 strip 内的所有点按 y 坐标排序。排序之后固定当前点 p只需要检查排在 p 后面的那些点 q。如果 p 和 q 的 y 坐标差已经大于等于 d那两点距离必然大于等于 d直接停止检查后面的点。因为 y 坐标递增后面的点只会离得更远。这个思路非常像滑动窗口对每个点只在一个高度为 d 的窗口里向后看。strip 内按 y 排序后的检查示意 y 坐标升序排列 (5,3) ← p1 (6,4) ← p2 → 与 p1 的 y 差 1 d需要比较 如果某点的 y 与 p1 的差超过 d就跳过。这样一来每个点不会跟 strip 里所有点比较最多只会跟 y 坐标差距小于 d 的那些点比较。那么接下来还有一个关键问题在一个高度为 d 的窗口里最多可能有多少个点如果这个数量是常数整个合并步骤就能做到 O(n)。3.3 几何证明的画图讲解为什么最多只能检查常数个点这个证明是整个分治法最近点对里最精彩的部分。想象一个宽 2d、高 d 的矩形p 点在这个矩形的左下角附近矩形内部包含了所有可能与 p 距离小于 d 的候选点。2d × d 矩形内的划分示意 --------------------------- | | | | | 格 A | 格 B | 格 C | | | | | --------------------------- | p所在 | 格 E | 格 F | | 格 D | | | ---------------------------把这个矩形切成 2 行 3 列共 6 个小矩形。每个小矩形的宽是 2d/3高是 d/2。算一下对角线长度sqrt((2d/3)² (d/2)²) d × sqrt(4/9 1/4) d × sqrt(16/36 9/36) d × sqrt(25/36) 5d/6对角线约等于 0.833d严格小于 d。这意味着什么如果一个格子里面放了两个点它们之间的距离会被限制在这个格子的对角线以内也就是必须小于 d。但我们知道 d 已经是左右两个子区域内找出来的最短距离了整个平面上不可能再有距离小于 d 的点对存在否则左右递归早就发现了。所以每个小矩形里最多只能有 1 个点。6 个小矩形加起来最多 6 个点再加上 p 点自己也不超过 7 个点。就算不同教材画法有差异有的切成 8 个小正方形核心结论都一样这个区域内点的数量是常数。所以每个点只需要向后检查固定数量的几个点就够了不需要看完整条 strip。4. 手把手画图演示完整流程4.1 递归过程的画图推演回到我设计的那组数据。8 个点按 x 排序后先分成左半和右半然后两边各自递归。递归树如下全部 8 个点 / \ 左半 4 个点 右半 4 个点 / \ / \ (1,30),(2,28) (3,31),(5,3) (6,4),(20,15) (21,13),(22,16) d√5 d√788 d√317 d√10 \ / \ / 左半合并 d√5 右半合并 d√5 \ / 全局合并跨线候选 d√2逐个看。左半 4 个点是 (1,30)、(2,28)、(3,31)、(5,3)。继续划分(1,30) 和 (2,28) 一组距离是 sqrt((1-2)²(30-28)²) sqrt(14) √5(3,31) 和 (5,3) 一组距离是 sqrt(4784) √788。左半合并时d 取 min(√5, √788) √5strip 区域宽度 2√5里面包含 (1,30)、(2,28)、(3,31)进一步检查后仍然没有更小值所以左半内部最近距离就是 √5。右半 4 个点是 (6,4)、(20,15)、(21,13)、(22,16)。(6,4) 和 (20,15) 距离 sqrt(196121) √317(21,13) 和 (22,16) 距离 sqrt(19) √10。右半合并时 d √10strip 内按 y 排序后有 (21,13)、(20,15)、(22,16)其中 (20,15) 和 (21,13) 的距离是 sqrt(14) √5比 √10 更小于是右半最近距离更新成 √5。此时全局上界 d min(√5, √5) √5。4.2 合并过程的画图推演跨线点对登场合并左半和右半时分割线取 x 5.5当前最优距离 d √5 ≈ 2.236。strip 区域的范围就是[5.5 - 2.236, 5.5 2.236] [3.264, 7.736]所有点里x 坐标落在这个区间的只有两个(5,3) 和 (6,4)。其他点要么在 strip 左边要么在右边直接排除。全局合并时的 strip y 4 B 3 L4 |← d2.236 →|← d2.236 →| x3.264 x5.5 x7.736 strip 内只有两个点 (5,3) 和 (6,4)strip 内按 y 排序后依然是 (5,3)、(6,4)。两个点之间 y 坐标差 1小于 d所以必须计算距离sqrt((5-6)² (3-4)²) sqrt(11) √2 ≈ 1.414√2 小于当前全局上界 √5于是答案更新为 √2。最终最近点对就是跨线的 (5,3) 和 (6,4)。这组数据特别适合演示分治的合并威力左半内部和右半内部各自的最短距离都是 √5但全局最短却是跨线的 √2。如果只看左右两半的结果永远发现不了这个更优答案。这也是为什么合并步骤绝不能省略的原因。4.3 画图理解为什么合并不会漏掉答案很多第一次学的人都会担心strip 里只检查这么点候选会不会把正确答案漏掉我当时也有这个怀疑。画一遍图之后其实就清楚了。假设真正的最优跨线点对是 a 和 b距离小于当前 d。a 和 b 分别在分割线两侧它们每个点到分割线的水平距离都必然小于它们之间的距离也就必然小于 d。所以 a 和 b 都一定在 strip 区域内不会被剪枝剪掉。这是合并步骤正确性的第一重保障。第二重保障是 y 坐标窗口。a 和 b 的 y 坐标差不会超过它们的距离也就小于 d。所以在按 y 排序后的序列里a 和 b 一定落在同一个高度为 d 的窗口内检查 a 时一定会看到 b。两重保障叠加答案不可能漏只是需要确保 check 的时候用严格的小于当前最优来判断。这不是玄学是几何性质给出的硬保证。5. 复杂度与正确性分析5.1 递推公式与 O(n log n)分治最近点对的时间复杂度需要认真算一下。设 T(n) 是处理 n 个点的时间递归时切成两个规模为 n/2 的子问题所以有 2T(n/2)。合并部分构造 strip 需要遍历 n 个点判断是否在区域内一次线性扫描O(n)。strip 内按 y 排序时如果每一层都重新排序排序是 O(m log m)其中 m 是 strip 内点数最坏情况下 m 接近 n合并就是 O(n log n)。于是递推公式有两种情况如果合并前对 strip 重新排序T(n) 2T(n/2) O(n log n)解出来 T(n) O(n log² n)。如果做预排序优化递归过程中始终保持 y 序列有序合并时直接线性归并T(n) 2T(n/2) O(n)解出来 T(n) O(n log n)。实际工程里我大多数时候用第一种简化实现因为数据量在几万以内两者差距不大。但如果是竞赛题或超大数据量必须用预排序优化。预排序的做法是所有点一开始按 x 排序进入递归同时在主函数里维护一个按 y 排序的全局序列递归时把序列按 x 中位数分成两份合并阶段线性地把两个有序 y 序列 merge 成一个。这样每一层都是 O(n)总复杂度稳定 O(n log n)。5.2 正确性论证的三个关键点分治算法能保证正确性靠的是三个环环相扣的结论。第一最优解只有三种可能位置全在左半、全在右半、跨分割线。递归处理前两种合并处理第三种覆盖了所有情况。第二跨线最优解的两个点必然都在 strip 内。这点前面已经证明过水平距离小于等于两点实际距离实际距离小于 d 就意味着水平距离小于 d。第三strip 内按 y 排序后每个点只需要检查后面有限个点。因为在一个高为 d 的窗口内点的数量有常数上界。只要窗口内的候选点没有被漏掉检查就不会错。这三个结论放在一起算法在逻辑上就是完备的。你可以用随机数据反复验证我实测过大量随机点集和暴力法对拍结果完全一致。5.3 排序优化的细节为什么预处理后合并可以做到线性经常有人问既然 strip 要按 y 排序能不能每层直接 sort可以但不优雅。每层 sort 会让复杂度多一个 log。预排序的核心思路是用空间换时间。一开始就把点按 y 坐标排好序然后在递归过程中保持这个顺序不被打乱。具体实现是每层递归拿到的是已经按 x 分好的左右两个子数组以及一个按 y 排好序的全局数组。按 y 排序的数组里逐个判断点属于左半还是右半分别放进两个临时数组合并阶段再把两个临时数组归并回 y 有序数组。这样每个点只在每一层被常数次扫描总时间 O(n log n)。这个优化对理解很重要。我在一开始学的时候只满足于能算出正确答案没想过排序带来的额外 log后来做大规模数据处理时才意识到这个差异。如果你的数据量超过几十万每层 sort 的 O(n log² n) 会明显拖慢速度预排序几乎是必须的。6. 工程实现与踩坑笔记6.1 一份可以直接跑的 Python 参考实现下面是我实际常用的分支限界风格写法加了不少注释。我用平方距离比较来避免开根号的浮点误差最后一步再开根。import math def sqdist(p1, p2): dx p1[0] - p2[0] dy p1[1] - p2[1] return dx * dx dy * dy def closest_pair(points): pts sorted(points) # 按 x 排序相同 x 按 y n len(pts) if n 2: return float(inf), None, None return _solve(pts, 0, n - 1) def _solve(pts, l, r): if l r: return float(inf), None, None if l 1 r: return sqdist(pts[l], pts[r]), pts[l], pts[r] mid (l r) // 2 mid_x pts[mid][0] dl, al, bl _solve(pts, l, mid) dr, ar, br _solve(pts, mid 1, r) if dl dr: best, pa, pb dl, al, bl else: best, pa, pb dr, ar, br # 收集 strip 内的候选点 strip [] for i in range(l, r 1): if abs(pts[i][0] - mid_x) best: strip.append(pts[i]) # 按 y 排序 strip.sort(keylambda p: p[1]) # 滑动窗口检查 m len(strip) for i in range(m): for j in range(i 1, m): if strip[j][1] - strip[i][1] best: break d sqdist(strip[i], strip[j]) if d best: best, pa, pb d, strip[i], strip[j] return best, pa, pb调用示例points [(1,30), (2,28), (3,31), (5,3), (6,4), (20,15), (21,13), (22,16)] d2, a, b closest_pair(points) print(a, b, math.sqrt(d2))输出结果是(5, 3)(6, 4)1.4142135623730951和前面手工推演完全一致。6.2 边界条件与递归出口递归出口是三件容易出问题的事。首先是单点情况区间里只有一个点没有点对直接返回无穷大。我的代码里用l r处理。其次是两个点的情况直接计算距离返回避免继续划分。不写这个出口的话两个点会被切成一个点加空区间空区间返回无穷大合并时 strip 扫一遍也能得到正确结果但多一层无意义递归代码也不清晰。第三是重复点。如果两个点坐标完全相同理论上它们的距离是 0是全局最优算法会立刻发现。但要注意 strip 收集条件里的浮点比较。如果 best 已经变成 0那 strip 里只有 x 完全相同的点滑动窗口依然能处理。最稳妥的做法还是在主函数一开始先做一次去重检测存在重复点直接返回 0。6.3 浮点精度与比较策略距离比较有一条小经验不要在递归内部用math.sqrt。开根号是浮点运算不但慢而且累积误差会让比较变得不干净。我全程用平方距离最后在返回时才开一次根。这样既快又准。另一个容易踩的坑是 strip 边界的等号判断。我建议用而不是。因为如果两个点的距离恰好等于当前最优值用把它们排除在 strip 外也不影响更新答案反正不会变得更优但用可以避免一些边界争议实现上更安全。不过要注意如果整个算法允许返回等距的多个解那必须用并且在比较时用更新。通常题目只要求任意一个最近点对所以代码里不必过度纠结。6.4 常见问题速查表现象可能原因解决方法答案偏大合并时漏了 strip 区域内的候选点检查 strip 收集条件确认用的是当前最优值 d答案偏大滑动窗口内提前 break确认 break 条件用的是 y 差值大于等于 d而不是大于复杂度退化到 O(n²)strip 内所有点两两都比较必须按 y 排序并用 y 差值剪枝重复点返回异常没有处理坐标完全相同的点主函数开头特判存在重复点直接返回 0浮点误差导致边界判断失误递归内部用开根后的距离做比较全程用平方距离比较最后再开根输出点对与暴力法不一致多个最优解选择了不同的一对只要距离相等任何一对都算正确不用纠结7. 写在最后画图理解与个人体会我个人在实际学习中的体会是像最近点对这种几何味很重的算法光看文字推导效率很低画图几乎是必须的。把点标在坐标系上画出分割线、画出 strip、画出按 y 排序后的滑动窗口整个算法的每一步都有了直观载体。我当年就是亲手在纸上把 8 个点的例子推演了一遍才彻底搞懂为什么合并阶段只需要检查常数个点。如果你也在学这个算法建议拿笔照着文中的 8 个点自己画一遍递归树再画一遍 strip 区域。画到合并那一步看到 (5,3) 和 (6,4) 这两个跨线的点在 strip 里相遇时那种原来如此的感觉是看多少篇文章都换不来的。最后再分享一个小技巧写完分治实现后一定写一个暴力解法做对拍随机生成几千组点集逐一比对结果。这个习惯帮我排查掉了大量边界 bug也是我写任何算法题都会做的第一件事。算法写出来是给人看的但正确性最终要靠数据说话。 
长河君 · 2026/10/13 22:37:42 · 阅读 1.2k 最近点对问题分治法详解：从暴力到O(n log n)的几何算法
最近点对问题Closest Pair of Points是我当年学算法时印象最深的一道题平面上给一堆点找出距离最近的两个点。暴力解法分分钟想到但数据量一上去就卡死。分治法的处理思路极其经典配合画图理解后整个证明和实现都会变得异常清晰。这篇文章我不仅会把分治法讲透还会用一套具体数据把每一步的图都画出来包括划分、递归、合并、候选区域这些关键环节看完你就能完整复现整个算法。1. 最近点对问题从暴力到分治的演进1.1 问题定义平面上找距离最近的两个点题目本身不复杂。假设平面上有 n 个点每个点用坐标 (x, y) 表示要求找出欧几里得距离最近的一对点。注意是点到点之间的直线距离d sqrt((x1-x2)² (y1-y2)²)这个问题的应用场景比我最初想的多。比如地理位置聚类里要找出距离最近的两个基站碰撞检测里要找出空间中距离最近的两个对象还有图像处理中的特征点匹配第一步往往都是找最近邻居。很多更大规模的问题会把最近点对当作一个子过程反复调用所以这个基础算法能不能跑得快直接影响整个系统的性能。我刚学的时候第一反应就是暴力法把所有点两两组合都算一遍距离记录最小值。两层循环搞定代码简单到不用思考。但问题在于复杂度。n 个点两两组合有 C(n,2) n(n-1)/2 种情况时间复杂度是 O(n²)。n 等于 1000 的时候大约要算 50 万次距离n 等于 10 万的时候就是 50 亿次。这个增长趋势会迅速击穿计算资源。实际项目中如果点集规模上了万O(n²) 的暴力解法基本就是不可用的必须找更聪明的办法。1.2 为什么暴力解会卡死规模增长的速度我拿一组实际数据感受一下。假设一秒钟能算 1000 万次距离已经是相当乐观的估算不同规模的点集会呈现这样的耗时点数量 n两两组合数量估算耗时1,000约 50 万0.05 秒10,000约 5000 万5 秒100,000约 50 亿500 秒1,000,000约 5000 亿50000 秒n 从 1 千涨到 100 万点数量只多了 1000 倍耗时却多了约 100 万倍。这就是 O(n²) 的可怕之处。而且这还只是距离计算还没算上距离比较、临时变量维护这些开销。真实场景里点动辄几十万个暴力法基本不可行。所以问题的关键变成了能不能把复杂度压到 O(n log n) 甚至 O(n)分治法正好能做到 O(n log n)而且思路非常符合直觉就是大事化小、小事化了。2. 分治法的整体设计与画图拆解2.1 三步走划分、递归、合并分治法处理最近点对的标准流程可以总结成三步。第一步划分。把所有点按照 x 坐标排序然后取中位数用一条垂直于 x 轴的线把点集分成左半和右半两部分两边点数尽量均衡。第二步递归。分别对左半部分和右半部分递归地求解最近点对得到左半内部的最近距离 dL 和右半内部的最近距离 dR。递归出口是区间里只有一个点或两个点一个点没有距离直接返回无穷大两个点直接算它们之间的距离。第三步合并。这是最关键的步骤。全局最近点对除了可能出现在左半内部或右半内部还有一种特殊情况一个点在左半一个点在右半它们跨越了分割线。这类跨线点对需要在合并时专门处理。合并的目标就是找出所有跨线点对中的最近距离然后跟 dL、dR 比较取最小值。这个三步走看起来平淡无奇但合并步骤里藏着一个几乎所有初学者都会忽略的优化点跨线点对到底要检查哪些点如果无脑把所有左半点和所有右半点两两比较那复杂度又回到 O(n²)分治就白做了。2.2 用一张图画清分治过程理解分治最好的方式就是画图。我用一组具体数据演示点集一共 8 个点随便编一组坐标但特意设计成跨线点对会成为最终答案这样合并步骤的意义才能体现出来。点集分布示意 y 31 L3 30 L1 28 L2 ... 16 R3 15 R1 13 R2 8 6 4 B 3 L4 ----------------------------------------------------------- x 1 2 3 4 5 6 7 8 9 ... 20 21 228 个点按 x 坐标排序后是编号坐标左/右半区L1(1, 30)左半L2(2, 28)左半L3(3, 31)左半L4(5, 3)左半B(6, 4)右半R1(20, 15)右半R2(21, 13)右半R3(22, 16)右半初始状态按 x 坐标排序后取中间位置把点集切成左右各 4 个。分割线画在 x 5.5 左右也就是 L4 和 B 之间。分割示意 y 31 L3 30 L1 28 L2 ... 16 R3 15 R1 13 R2 4 B 3 L4 |← 左半4个点 →|← 右半4个点 →| x5.5后面整个算法的推演我都会基于这张图来讲。你看到的是先竖着切一刀左右各自找最短再检查跨线区域这套逻辑配上图就完全不会乱。3. 合并步骤真正的大 Boss3.1 strip 区域哪些点值得检查合并时的朴素做法是把左半所有点和右半所有点都两两算一遍。但这显然不行。仔细想想就会发现大部分跨线点对根本不可能成为最优解。已知当前最佳的左右内部距离是 d min(dL, dR)。如果跨线点对的距离要小于 d那么这两个点的 x 坐标都不能离分割线太远。具体来说任何一个点如果它的 x 坐标与分割线的水平距离已经大于等于 d那它跟对面任何一个点的距离都不可能小于 d。因为欧几里得距离必然大于等于水平方向的差距。所以真正值得检查的候选区域是以分割线为中心、宽度为 2d 的一条竖直带状区域通常叫 strip。分割线左边 d 宽右边 d 宽。strip 区域示意 y 31 L3 30 L1 28 L2 ... 16 R3 15 R1 13 R2 4 B 3 L4 | | | |← d →| | strip左边界 分割线 strip右边界 x5.5-d x5.5 x5.5dstrip 区域之外的点直接忽略因为它们在水平方向上就不够格。这个剪枝让候选点数量大幅减少。但问题还没完全解决如果点分布很密strip 里可能依然有大量点全两两比较还是灾难。3.2 在 strip 内按 y 坐标排序滑动窗口的思想strip 内的点不能继续用 x 方向来剪枝了因为它们 x 方向都在分割线附近。这里换一个思路把 strip 内的所有点按 y 坐标排序。排序之后固定当前点 p只需要检查排在 p 后面的那些点 q。如果 p 和 q 的 y 坐标差已经大于等于 d那两点距离必然大于等于 d直接停止检查后面的点。因为 y 坐标递增后面的点只会离得更远。这个思路非常像滑动窗口对每个点只在一个高度为 d 的窗口里向后看。strip 内按 y 排序后的检查示意 y 坐标升序排列 (5,3) ← p1 (6,4) ← p2 → 与 p1 的 y 差 1 d需要比较 如果某点的 y 与 p1 的差超过 d就跳过。这样一来每个点不会跟 strip 里所有点比较最多只会跟 y 坐标差距小于 d 的那些点比较。那么接下来还有一个关键问题在一个高度为 d 的窗口里最多可能有多少个点如果这个数量是常数整个合并步骤就能做到 O(n)。3.3 几何证明的画图讲解为什么最多只能检查常数个点这个证明是整个分治法最近点对里最精彩的部分。想象一个宽 2d、高 d 的矩形p 点在这个矩形的左下角附近矩形内部包含了所有可能与 p 距离小于 d 的候选点。2d × d 矩形内的划分示意 --------------------------- | | | | | 格 A | 格 B | 格 C | | | | | --------------------------- | p所在 | 格 E | 格 F | | 格 D | | | ---------------------------把这个矩形切成 2 行 3 列共 6 个小矩形。每个小矩形的宽是 2d/3高是 d/2。算一下对角线长度sqrt((2d/3)² (d/2)²) d × sqrt(4/9 1/4) d × sqrt(16/36 9/36) d × sqrt(25/36) 5d/6对角线约等于 0.833d严格小于 d。这意味着什么如果一个格子里面放了两个点它们之间的距离会被限制在这个格子的对角线以内也就是必须小于 d。但我们知道 d 已经是左右两个子区域内找出来的最短距离了整个平面上不可能再有距离小于 d 的点对存在否则左右递归早就发现了。所以每个小矩形里最多只能有 1 个点。6 个小矩形加起来最多 6 个点再加上 p 点自己也不超过 7 个点。就算不同教材画法有差异有的切成 8 个小正方形核心结论都一样这个区域内点的数量是常数。所以每个点只需要向后检查固定数量的几个点就够了不需要看完整条 strip。4. 手把手画图演示完整流程4.1 递归过程的画图推演回到我设计的那组数据。8 个点按 x 排序后先分成左半和右半然后两边各自递归。递归树如下全部 8 个点 / \ 左半 4 个点 右半 4 个点 / \ / \ (1,30),(2,28) (3,31),(5,3) (6,4),(20,15) (21,13),(22,16) d√5 d√788 d√317 d√10 \ / \ / 左半合并 d√5 右半合并 d√5 \ / 全局合并跨线候选 d√2逐个看。左半 4 个点是 (1,30)、(2,28)、(3,31)、(5,3)。继续划分(1,30) 和 (2,28) 一组距离是 sqrt((1-2)²(30-28)²) sqrt(14) √5(3,31) 和 (5,3) 一组距离是 sqrt(4784) √788。左半合并时d 取 min(√5, √788) √5strip 区域宽度 2√5里面包含 (1,30)、(2,28)、(3,31)进一步检查后仍然没有更小值所以左半内部最近距离就是 √5。右半 4 个点是 (6,4)、(20,15)、(21,13)、(22,16)。(6,4) 和 (20,15) 距离 sqrt(196121) √317(21,13) 和 (22,16) 距离 sqrt(19) √10。右半合并时 d √10strip 内按 y 排序后有 (21,13)、(20,15)、(22,16)其中 (20,15) 和 (21,13) 的距离是 sqrt(14) √5比 √10 更小于是右半最近距离更新成 √5。此时全局上界 d min(√5, √5) √5。4.2 合并过程的画图推演跨线点对登场合并左半和右半时分割线取 x 5.5当前最优距离 d √5 ≈ 2.236。strip 区域的范围就是[5.5 - 2.236, 5.5 2.236] [3.264, 7.736]所有点里x 坐标落在这个区间的只有两个(5,3) 和 (6,4)。其他点要么在 strip 左边要么在右边直接排除。全局合并时的 strip y 4 B 3 L4 |← d2.236 →|← d2.236 →| x3.264 x5.5 x7.736 strip 内只有两个点 (5,3) 和 (6,4)strip 内按 y 排序后依然是 (5,3)、(6,4)。两个点之间 y 坐标差 1小于 d所以必须计算距离sqrt((5-6)² (3-4)²) sqrt(11) √2 ≈ 1.414√2 小于当前全局上界 √5于是答案更新为 √2。最终最近点对就是跨线的 (5,3) 和 (6,4)。这组数据特别适合演示分治的合并威力左半内部和右半内部各自的最短距离都是 √5但全局最短却是跨线的 √2。如果只看左右两半的结果永远发现不了这个更优答案。这也是为什么合并步骤绝不能省略的原因。4.3 画图理解为什么合并不会漏掉答案很多第一次学的人都会担心strip 里只检查这么点候选会不会把正确答案漏掉我当时也有这个怀疑。画一遍图之后其实就清楚了。假设真正的最优跨线点对是 a 和 b距离小于当前 d。a 和 b 分别在分割线两侧它们每个点到分割线的水平距离都必然小于它们之间的距离也就必然小于 d。所以 a 和 b 都一定在 strip 区域内不会被剪枝剪掉。这是合并步骤正确性的第一重保障。第二重保障是 y 坐标窗口。a 和 b 的 y 坐标差不会超过它们的距离也就小于 d。所以在按 y 排序后的序列里a 和 b 一定落在同一个高度为 d 的窗口内检查 a 时一定会看到 b。两重保障叠加答案不可能漏只是需要确保 check 的时候用严格的小于当前最优来判断。这不是玄学是几何性质给出的硬保证。5. 复杂度与正确性分析5.1 递推公式与 O(n log n)分治最近点对的时间复杂度需要认真算一下。设 T(n) 是处理 n 个点的时间递归时切成两个规模为 n/2 的子问题所以有 2T(n/2)。合并部分构造 strip 需要遍历 n 个点判断是否在区域内一次线性扫描O(n)。strip 内按 y 排序时如果每一层都重新排序排序是 O(m log m)其中 m 是 strip 内点数最坏情况下 m 接近 n合并就是 O(n log n)。于是递推公式有两种情况如果合并前对 strip 重新排序T(n) 2T(n/2) O(n log n)解出来 T(n) O(n log² n)。如果做预排序优化递归过程中始终保持 y 序列有序合并时直接线性归并T(n) 2T(n/2) O(n)解出来 T(n) O(n log n)。实际工程里我大多数时候用第一种简化实现因为数据量在几万以内两者差距不大。但如果是竞赛题或超大数据量必须用预排序优化。预排序的做法是所有点一开始按 x 排序进入递归同时在主函数里维护一个按 y 排序的全局序列递归时把序列按 x 中位数分成两份合并阶段线性地把两个有序 y 序列 merge 成一个。这样每一层都是 O(n)总复杂度稳定 O(n log n)。5.2 正确性论证的三个关键点分治算法能保证正确性靠的是三个环环相扣的结论。第一最优解只有三种可能位置全在左半、全在右半、跨分割线。递归处理前两种合并处理第三种覆盖了所有情况。第二跨线最优解的两个点必然都在 strip 内。这点前面已经证明过水平距离小于等于两点实际距离实际距离小于 d 就意味着水平距离小于 d。第三strip 内按 y 排序后每个点只需要检查后面有限个点。因为在一个高为 d 的窗口内点的数量有常数上界。只要窗口内的候选点没有被漏掉检查就不会错。这三个结论放在一起算法在逻辑上就是完备的。你可以用随机数据反复验证我实测过大量随机点集和暴力法对拍结果完全一致。5.3 排序优化的细节为什么预处理后合并可以做到线性经常有人问既然 strip 要按 y 排序能不能每层直接 sort可以但不优雅。每层 sort 会让复杂度多一个 log。预排序的核心思路是用空间换时间。一开始就把点按 y 坐标排好序然后在递归过程中保持这个顺序不被打乱。具体实现是每层递归拿到的是已经按 x 分好的左右两个子数组以及一个按 y 排好序的全局数组。按 y 排序的数组里逐个判断点属于左半还是右半分别放进两个临时数组合并阶段再把两个临时数组归并回 y 有序数组。这样每个点只在每一层被常数次扫描总时间 O(n log n)。这个优化对理解很重要。我在一开始学的时候只满足于能算出正确答案没想过排序带来的额外 log后来做大规模数据处理时才意识到这个差异。如果你的数据量超过几十万每层 sort 的 O(n log² n) 会明显拖慢速度预排序几乎是必须的。6. 工程实现与踩坑笔记6.1 一份可以直接跑的 Python 参考实现下面是我实际常用的分支限界风格写法加了不少注释。我用平方距离比较来避免开根号的浮点误差最后一步再开根。import math def sqdist(p1, p2): dx p1[0] - p2[0] dy p1[1] - p2[1] return dx * dx dy * dy def closest_pair(points): pts sorted(points) # 按 x 排序相同 x 按 y n len(pts) if n 2: return float(inf), None, None return _solve(pts, 0, n - 1) def _solve(pts, l, r): if l r: return float(inf), None, None if l 1 r: return sqdist(pts[l], pts[r]), pts[l], pts[r] mid (l r) // 2 mid_x pts[mid][0] dl, al, bl _solve(pts, l, mid) dr, ar, br _solve(pts, mid 1, r) if dl dr: best, pa, pb dl, al, bl else: best, pa, pb dr, ar, br # 收集 strip 内的候选点 strip [] for i in range(l, r 1): if abs(pts[i][0] - mid_x) best: strip.append(pts[i]) # 按 y 排序 strip.sort(keylambda p: p[1]) # 滑动窗口检查 m len(strip) for i in range(m): for j in range(i 1, m): if strip[j][1] - strip[i][1] best: break d sqdist(strip[i], strip[j]) if d best: best, pa, pb d, strip[i], strip[j] return best, pa, pb调用示例points [(1,30), (2,28), (3,31), (5,3), (6,4), (20,15), (21,13), (22,16)] d2, a, b closest_pair(points) print(a, b, math.sqrt(d2))输出结果是(5, 3)(6, 4)1.4142135623730951和前面手工推演完全一致。6.2 边界条件与递归出口递归出口是三件容易出问题的事。首先是单点情况区间里只有一个点没有点对直接返回无穷大。我的代码里用l r处理。其次是两个点的情况直接计算距离返回避免继续划分。不写这个出口的话两个点会被切成一个点加空区间空区间返回无穷大合并时 strip 扫一遍也能得到正确结果但多一层无意义递归代码也不清晰。第三是重复点。如果两个点坐标完全相同理论上它们的距离是 0是全局最优算法会立刻发现。但要注意 strip 收集条件里的浮点比较。如果 best 已经变成 0那 strip 里只有 x 完全相同的点滑动窗口依然能处理。最稳妥的做法还是在主函数一开始先做一次去重检测存在重复点直接返回 0。6.3 浮点精度与比较策略距离比较有一条小经验不要在递归内部用math.sqrt。开根号是浮点运算不但慢而且累积误差会让比较变得不干净。我全程用平方距离最后在返回时才开一次根。这样既快又准。另一个容易踩的坑是 strip 边界的等号判断。我建议用而不是。因为如果两个点的距离恰好等于当前最优值用把它们排除在 strip 外也不影响更新答案反正不会变得更优但用可以避免一些边界争议实现上更安全。不过要注意如果整个算法允许返回等距的多个解那必须用并且在比较时用更新。通常题目只要求任意一个最近点对所以代码里不必过度纠结。6.4 常见问题速查表现象可能原因解决方法答案偏大合并时漏了 strip 区域内的候选点检查 strip 收集条件确认用的是当前最优值 d答案偏大滑动窗口内提前 break确认 break 条件用的是 y 差值大于等于 d而不是大于复杂度退化到 O(n²)strip 内所有点两两都比较必须按 y 排序并用 y 差值剪枝重复点返回异常没有处理坐标完全相同的点主函数开头特判存在重复点直接返回 0浮点误差导致边界判断失误递归内部用开根后的距离做比较全程用平方距离比较最后再开根输出点对与暴力法不一致多个最优解选择了不同的一对只要距离相等任何一对都算正确不用纠结7. 写在最后画图理解与个人体会我个人在实际学习中的体会是像最近点对这种几何味很重的算法光看文字推导效率很低画图几乎是必须的。把点标在坐标系上画出分割线、画出 strip、画出按 y 排序后的滑动窗口整个算法的每一步都有了直观载体。我当年就是亲手在纸上把 8 个点的例子推演了一遍才彻底搞懂为什么合并阶段只需要检查常数个点。如果你也在学这个算法建议拿笔照着文中的 8 个点自己画一遍递归树再画一遍 strip 区域。画到合并那一步看到 (5,3) 和 (6,4) 这两个跨线的点在 strip 里相遇时那种原来如此的感觉是看多少篇文章都换不来的。最后再分享一个小技巧写完分治实现后一定写一个暴力解法做对拍随机生成几千组点集逐一比对结果。这个习惯帮我排查掉了大量边界 bug也是我写任何算法题都会做的第一件事。算法写出来是给人看的但正确性最终要靠数据说话。