基于排序的“最近点对”问题的分治求解算法

题目描述
在二维平面上给定一组点，需要找到距离最小的一对点（即最近点对）。给定 n 个点，每个点用坐标 (x, y) 表示，要求设计一个比朴素 O(n²) 更高效的算法，输出最小距离。

解题过程

步骤1：理解问题与朴素解法

1. 输入：n 个点的列表，每个点有横纵坐标。
2. 输出：最近两点之间的欧几里得距离。
3. 朴素方法：比较所有点对，计算距离并取最小值。时间复杂度为 O(n²)，在 n 很大时效率很低。

步骤2：分治策略的初步构想

1. 分治法的核心思路：
   • 将点集划分为左右两半，分别递归求解左右子集的最近点对距离，记为 δ_left 和 δ_right。
   • 取 δ = min(δ_left, δ_right)。
   • 关键挑战：最近点对可能由一个点在左半部分、一个点在右半部分（即跨越分界线）。需要高效检查这种“跨越”点对。
2. 分治的优势：如果能将“跨越检查”控制在 O(n) 时间内，则总时间复杂度可降至 O(n log n)。

步骤3：对点进行预处理排序

1. 为便于分治，我们预先将点按照 x 坐标排序，得到有序数组 P_x。排序时间复杂度 O(n log n)。
2. 为什么排序？在递归分割时，可以快速按 x 坐标将点集对半划分（例如取中间点的 x 坐标作为分界线）。
3. 同时，为了高效检查跨越分界线的点对，我们还需要按 y 坐标排序的数组副本 P_y，但 P_y 的维护需要在递归中小心处理，以避免每次递归都重新排序（否则会退化为 O(n²)）。

步骤4：分治算法的详细步骤

1. 递归基本情况：
   • 若点数 n ≤ 3，直接计算所有点对距离，返回最小值。
2. 划分阶段：
   • 用 P_x 中间点的 x 坐标 mid_x 将点集划分为左半部 Q 和右半部 R（点按 P_x 顺序自然分割）。
   • 同时，我们需要得到左半部点按 y 排序的数组 Q_y 和右半部点按 y 排序的数组 R_y。这可以在递归前通过一次对 P_y 的扫描完成：根据点的 x 坐标是否小于 mid_x，将其分配到 Q_y 或 R_y，同时保持它们在 P_y 中的顺序（即保持 y 有序）。
3. 递归求解：
   • 递归调用分别求解 (Q, Q_y) 和 (R, R_y)，得到 δ_left 和 δ_right。
   • 令 δ = min(δ_left, δ_right)。
4. 检查跨越分界线的点对：
   • 只需考虑那些 x 坐标在 [mid_x - δ, mid_x + δ] 范围内的点，因为这些点才可能与另一侧的点距离小于 δ。
   • 如何快速得到这些点？我们有一个按 y 排序的整个点集数组 P_y。我们可以扫描 P_y，收集所有 x 坐标在范围内的点，构成数组 S（S 中的点已按 y 排序）。
   • 对 S 中的每个点，检查与其后面最多 7 个点之间的距离。这是因为：在 δ × 2δ 的矩形区域内，最多只能容纳 8 个点使得任意两点距离 ≥ δ（这可以通过几何鸽巢原理证明）。因此，每个点只需检查常数个后续点。
   • 在检查过程中更新最小距离 δ。
5. 返回最终的 δ。

步骤5：时间复杂度分析

1. 预处理排序：O(n log n)。
2. 递归方程：T(n) = 2T(n/2) + O(n)（划分和跨越检查均为 O(n)）。
3. 由主定理可得，总时间复杂度为 O(n log n)。空间复杂度 O(n)，用于存储排序数组。

步骤6：关键证明细节

1. 为什么只需检查后面最多 7 个点？
   • 考虑 S 中按 y 排序的点 p。在 y 方向，与 p 距离小于 δ 的点必须落在以 p 为中心、高度为 2δ 的矩形内。
   • 将该矩形划分为 8 个 δ/2 高的小格子。由于左右两侧各自的最小点对距离至少为 δ，每个小格子内最多只能有一个点（否则格子内两点距离将小于 δ）。因此，p 之后需要检查的点不超过 7 个。
2. 如何维护按 y 排序的数组而不增加复杂度？
   • 在递归分割时，通过一次扫描 P_y，将点分配到 Q_y 和 R_y，这个过程是 O(n) 的，且保持了 y 有序性。因此，整个递归过程中，每个递归层级的总扫描代价为 O(n)。

步骤7：伪代码描述

function ClosestPair(P_x, P_y):
    if |P_x| ≤ 3:
        直接计算并返回最小距离
    mid = floor(|P_x| / 2)
    用 P_x[mid].x 作为分界线
    构造 Q_y, R_y （通过扫描 P_y）
    δ_left = ClosestPair(P_x[0:mid], Q_y)
    δ_right = ClosestPair(P_x[mid:], R_y)
    δ = min(δ_left, δ_right)
    从 P_y 中收集所有满足 |x - mid_x| < δ 的点，存入 S（保持 y 顺序）
    for i = 0 to |S|-1:
        for j = i+1 to min(i+7, |S|-1):
            if S[j].y - S[i].y ≥ δ: break
            δ = min(δ, distance(S[i], S[j]))
    return δ

初始化调用时，先对点按 x 排序得到 P_x，按 y 排序得到 P_y，然后调用 ClosestPair(P_x, P_y)。

总结
本问题展示了排序在分治算法中的关键作用：通过预排序（按 x 和 y）将二维最近点对问题转化为可高效递归分解的结构，并将跨越分界线的检查控制在 O(n) 时间，最终达到 O(n log n) 的最优时间复杂度。该算法是计算几何中的经典范例，结合了排序、分治和几何剪枝技巧。