最近点对

What · 是什么

给定平面上 n 个点，求其中欧几里得距离最近的一对点。朴素两两枚举 O(n²)。分治算法 O(n log n)：按 x 坐标排序并从中点切分，递归求左右两半各自最近距离 h=min(h1,h2)，然后只需检查横坐标距分割线 < h 的『条带』内的点——条带内按 y 排序，对每个点只检查其后 y 差 < h 的常数个点（最多 7 个）。Shamos-Hoey（1975）提出，Preparata & Shamos 证明其在决策树模型下最优。另有 Rabin 的随机化线性期望算法（网格分桶）。

Why · 为什么

How · 实现

伪代码

# 按 x 排序, 递归 rec(l,r):
def rec(l, r):
  if r-l <= 3: 暴力更新最近对; 按y排序; return
  m = (l+r)//2; midx = x[m]
  rec(l,m); rec(m,r)
  merge 两半按y (归并)
  for i in [l..r):
    if |x[i]-midx| < h:
      for j in strip, j<i, y差<h:
        update(pair)
  return 按y排序后的数组

Python 实现

import math


def closest_pair(points):
    """分治求最近点对. points: [(x,y)] 浮点/整数.
    返回 (dist, (i, j)) 距离与两个点的原始索引."""
    n = len(points)
    pts = list(points)
    order = list(range(n))
    pts = sorted(zip(pts, order), key=lambda t: (t[0][0], t[0][1]))
    best = float('inf')
    best_pair = None

    def dist2(p, q):
        return (p[0] - q[0]) ** 2 + (p[1] - q[1]) ** 2

    def upd(p, q):
        nonlocal best, best_pair
        d = dist2(p[0], q[0])
        if d < best:
            best = d
            best_pair = (p[1], q[1])

    arr = pts
    buf = [None] * n

    def rec(l, r):
        """处理 arr[l:r), 返回后该段按 y 排序."""
        nonlocal best
        if r - l <= 3:
            for i in range(l, r):
                for j in range(i + 1, r):
                    upd(arr[i], arr[j])
            arr[l:r] = sorted(arr[l:r], key=lambda t: t[0][1])
            return
        m = (l + r) // 2
        midx = arr[m][0][0]
        rec(l, m)
        rec(m, r)
        # 归并按 y
        i, j, k = l, m, l
        while i < m and j < r:
            if arr[i][0][1] <= arr[j][0][1]:
                buf[k] = arr[i]; i += 1
            else:
                buf[k] = arr[j]; j += 1
            k += 1
        while i < m:
            buf[k] = arr[i]; i += 1; k += 1
        while j < r:
            buf[k] = arr[j]; j += 1; k += 1
        arr[l:r] = buf[l:r]
        # 条带检查
        strip = []
        for k in range(l, r):
            if abs(arr[k][0][0] - midx) < best ** 0.5:
                strip.append(arr[k])
        for a in range(len(strip)):
            b = a - 1
            while b >= 0 and strip[a][0][1] - strip[b][0][1] < best ** 0.5:
                upd(strip[a], strip[b])
                b -= 1

    rec(0, n)
    return math.sqrt(best), best_pair


def brute(points):
    n = len(points)
    bd = float('inf'); bp = None
    for i in range(n):
        for j in range(i + 1, n):
            d = (points[i][0] - points[j][0]) ** 2 + (points[i][1] - points[j][1]) ** 2
            if d < bd:
                bd = d; bp = (i, j)
    return math.sqrt(bd), bp


if __name__ == "__main__":
    # 已知: 最近距离 1 (点(0,0)-(1,0))
    pts = [(0, 0), (1, 0), (10, 10), (11, 10), (5, 7)]
    d, p = closest_pair(pts)
    assert abs(d - 1.0) < 1e-9, d
    # 重合点 -> 0
    pts2 = [(3, 3), (3, 3), (9, 9)]
    d, _ = closest_pair(pts2)
    assert abs(d - 0.0) < 1e-9
    # 边界: 2 个点
    pts3 = [(0, 0), (4, 3)]
    d, _ = closest_pair(pts3)
    assert abs(d - 5.0) < 1e-9

    # 随机交叉验证
    import random
    random.seed(2026)
    for _ in range(200):
        n = random.randint(2, 60)
        pts = [(random.randint(-100, 100), random.randint(-100, 100)) for _ in range(n)]
        d1, p1 = closest_pair(pts)
        d2, p2 = brute(pts)
        assert abs(d1 - d2) < 1e-7, (n, d1, d2)
        # 校验返回的点对确实距离 d1
        i, j = p1
        assert abs(((pts[i][0] - pts[j][0]) ** 2 + (pts[i][1] - pts[j][1]) ** 2) ** 0.5 - d1) < 1e-9
    print("All tests passed.")

易错点

• 合并时条带检查忘记按 y 排序就遍历，退化为 O(n²)
• 用 x 坐标绝对差 < h 过滤条带，但 h 中途更新后要用最新 h 重新过滤
• 条带内检查方向：只查 y 小于当前点的（避免重复配对）
• 按 y 归并是必须的，否则每层 sort 复杂度错
• 递归终止条件 r-l≤3 用暴力，别在 0/1 点集上做跨立检查
• 浮点 sqrt 高频调用慢；整点用平方比较
• 返回的点对索引要映射回原始输入顺序（排序后索引偏移）

例题

信源

• OI Wiki✓ https://oi-wiki.org/geometry/nearest-points/
• CP-Algorithms✓ https://cp-algorithms.com/geometry/nearest_points.html
• 书籍✓ CPH ch29 Geometry (p291-304)