concept · closest pair

平面里最近的两个点怎么找？

给平面上 n 个点，找出距离最近的那一对。两两比一遍当然行，但那是 $O(n^2)$ ——一万个点就要算五千万次。分治法能做到 $O(n \log n)$ ，关键在一个几何观察：跨过中线的更近点对，只可能发生在一条很窄的带状区内。

在画布里拖动点看最近对实时更新。下面先用暴力法给出基准结果（它一定正确），再点**「分治法」**分五步看它如何用更少的比较得到同一答案。

1 · 分治三步：divide → conquer → 合并那条带

分：按 x 坐标找中位数，一条竖线把点切成左右两半。治：左右两半各自递归求出最近对，取较小的那个距离记作 d。合并：可能还有「一个点在左、一个点在右」的更近对被忽略了。但它们必须都落在中线两侧宽 d 的带状区里（否则光是横向就超过 d 了）。更妙的是：把带内的点按 y 排序后，每个点最多只需和接下来的常数个 (≤7) 点比较——因为一个 $d\times 2d$ 的小框里塞不下太多「彼此距离 ≥ d」的点。于是合并也是线性的。

递推式 T(n) = 2T(n/2) + O(n) → $O(n \log n)$ （和归并排序同款）。本页点少，左右两半的「递归结果」直接用朴素求得，但带状区那一刀的威力照样看得见：看右下角比较次数，分治通常远少于暴力的 C(n,2)。

2 · 边界情形 / 工程细节

带宽是严格的 < d：正好等于 d 的点不可能构成更近对，可放心排除。实现里为避免每层都重排，常预排序一次 x、并在递归中顺带维护按 y 排序的列表（类似归并），才真正落到 $O(n \log n)$ ；否则每层都 sort 会退化成 $O(n \log ^2 n)$ 。退化情形：很多点共线或重合时，带状区可能容纳不少点，但「≤ 常数个邻居」的界依然成立。

3 · 它用在哪里

碰撞检测 / 物理引擎（找最先可能相撞的一对）、地图与 LBS（最近的两个兴趣点 / 设施）、聚类与去重（最近邻是层次聚类、噪声点判定的基础）、图形学（网格简化、采样点间距）。它也是「分治 + 几何剪枝」这一招的范本——和线段树「能整片处理就别细究」、分支限界用 bound 剪掉大片解空间，是同一种思维。