平面最近点对

周子力大约 8 分钟教学文档算法设计与分析分治法递归计算几何高难度Python

平面最近点对

题目描述

给定至少两个平面点 points，每个点为整数坐标 $(x,y)$ ，寻找欧氏距离最小的两个不同输入位置。允许负坐标、相同横坐标以及重复坐标，不修改输入。

点的编号为其输入下标，从0开始。即使坐标相同，只要输入下标不同，也视为两个可配对的点，此时最小距离为0。若有多个最优点对，返回其中任意一对；不足两个点时抛出 ValueError。

为避免浮点开方带来的误差，返回格式为 (最小距离的平方, (点编号i, 点编号j))。编号对按 $i<j$ 排列，实际最短距离是返回平方值的平方根。

示例： 输入 [(0,0), (2,3), (3,3), (8,0)]，返回 (1, (1,2))，对应点 $(2,3)$ 与 $(3,3)$ ，距离为1。

直接枚举需要比较 $n(n-1)/2$ 对点。本题通过均衡分治及几何约束，将跨区域候选限制在线性数量级。

题目分析

子调用既返回答案，也返回纵向顺序

先将点连同原始编号按 (x,y,编号) 排序，然后按排序后的位置中点分成左右两半。这样即使所有横坐标相同，也能保证两侧点数均衡。

定义 solve(xs)：输入一组按横坐标有序的点，返回该组的最小距离平方、对应编号对，以及同组点按 (y,x,编号) 排列的新列表。

不超过3个点时直接枚举。更大规模分别求左右答案，取较小距离 $\delta$ ，再检查是否有距离小于 $\delta$ 的跨侧点对。子调用返回的纵向列表通过线性合并得到父区域的纵向列表，避免每层重新排序。

只检查分界线附近的条带

令分界横坐标为右半区首点的 x。横向距离分界线至少 $\delta$ 的点，不可能参与一个比 $\delta$ 更近的跨侧点对。因此只保留满足 $|x-x_{mid}|<\delta$ 的点。

这些点已经按纵坐标有序。对每个点，只需检查其后最多7个点；当纵坐标差已达到当前最小距离时，可以更早停止。代码始终比较平方值，不实际计算 $\delta$ 的平方根。

“7个”的依据是几何装箱：对一个点上方高为 $\delta$ 、宽为 $2\delta$ 的候选区域，左右各自分成4个边长 $\delta/2$ 的小格。同一半区内的点距至少 $\delta$ ，而小格对角线小于 $\delta$ ，所以每格至多有一个该半区点。最多8个点包含当前点，后继候选至多7个。分界线上的点仍按左右成员归属分析。该常数界可参照 CMU 最近点对讲义open in new window。

若子区域已有距离0，便不可能再改善，条带为空也可直接保留此答案。扫描中缩小了距离后，继续沿原条带检查仍然安全，只会增加可排除的候选。

正确性依据

最优点对要么在左半区内部，要么在右半区内部，要么跨越分界线。前两类由递归求出；第三类若能改善当前答案，必定位于条带内，纵向差小于当前距离，并包含在有限后继候选中。三类覆盖全部可能，取最小者就是当前问题的答案。

实现代码

Python 分治与条带扫描实现

def closest_pair(points):
    if len(points) < 2:
        raise ValueError("至少需要两个点")
    ordered = sorted((x, y, i) for i, (x, y) in enumerate(points))

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

    def pair_ids(p, q):
        return tuple(sorted((p[2], q[2])))

    def merge_y(left, right):
        result = []
        i = j = 0
        while i < len(left) and j < len(right):
            p, q = left[i], right[j]
            if (p[1], p[0], p[2]) <= (q[1], q[0], q[2]):
                result.append(p)
                i += 1
            else:
                result.append(q)
                j += 1
        result.extend(left[i:])
        result.extend(right[j:])
        return result

    def solve(xs):
        if len(xs) <= 3:
            best = distance2(xs[0], xs[1])
            pair = pair_ids(xs[0], xs[1])
            for i in range(len(xs)):
                for j in range(i + 1, len(xs)):
                    candidate = distance2(xs[i], xs[j])
                    if candidate < best:
                        best, pair = candidate, pair_ids(xs[i], xs[j])
            return best, pair, sorted(xs, key=lambda p: (p[1], p[0], p[2]))

        mid = len(xs) // 2
        split_x = xs[mid][0]
        left_d, left_pair, left_y = solve(xs[:mid])
        right_d, right_pair, right_y = solve(xs[mid:])
        if left_d <= right_d:
            best, pair = left_d, left_pair
        else:
            best, pair = right_d, right_pair

        by_y = merge_y(left_y, right_y)
        strip = [p for p in by_y if (p[0] - split_x) ** 2 < best]
        for i, p in enumerate(strip):
            for j in range(i + 1, min(i + 8, len(strip))):
                q = strip[j]
                if (q[1] - p[1]) ** 2 >= best:
                    break
                candidate = distance2(p, q)
                if candidate < best:
                    best, pair = candidate, pair_ids(p, q)
        return best, pair, by_y

    best, pair, _ = solve(ordered)
    return best, pair


for points in [
    [(0, 0), (2, 3), (3, 3), (8, 0)],
    [(0, 0), (3, 4)],
    [(2, 2), (2, 2), (9, 9)],
]:
    print(closest_pair(points))

输出：

(1, (1, 2))
(25, (0, 1))
(0, (0, 1))

根输入至少有两个点，规模至少4时才划分，两个子区也都至少有两个点。因此枚举边界可以安全读取 xs[0] 和 xs[1]。只在常数规模边界排序纵坐标，其余层用 merge_y。

算法执行过程

主示例已按横坐标排列，中点位置为2，分界线为 $x=3$ 。

阶段	状态或计算	结果
左半区	编号0、1，距离平方 $2^2+3^2$	13，点对 `(0,1)`
右半区	编号2、3，距离平方 $5^2+(-3)^2$	34，点对 `(2,3)`
合并两侧答案	取较小平方值	`best=13`
合并纵向顺序	编号依次为0、3、1、2	按 `(y,x,编号)` 有序
筛选条带	到 $x=3$ 的横向距离平方小于13	编号依次为0、1、2；编号3被排除
检查编号0的后继	到编号1平方13，到编号2平方18	均未改善
检查编号1的后继	到编号2平方1	更新为 `(1,(1,2))`

这里最优点对跨越分界线。如果只取两侧递归答案，会错误地返回距离平方13。若所有点横坐标相同，也仍按排序后的位置划分，不能用 x < split_x 把点全放到一边。

复杂度分析

按坐标比较、整数距离计算和元素读写为单位成本，令点数为 $n\geq2$ ；若坐标整数的位数很大，还需另计大整数运算成本。

时间复杂度： $O(n\log n)$ 。初始横坐标排序花费 $O(n\log n)$ ；每层划分列表、合并纵向列表、筛选条带均为线性，每个条带点检查至多7个后继。因此递推为 $T(n)=2T(n/2)+O(n)$ ，奇数长度时两侧相差1。

如果在每一层对全部条带点重新排序，当前层最坏成本变为 $O(n\log n)$ ，整体最坏上界变为 $O(n\log^2 n)$ 。维护并返回纵向顺序，是本实现达到上述复杂度的关键。

辅助空间复杂度： $O(n)$ ，包括排序结果、递归切片、纵向合并列表和条带；栈深度为 $O(\log n)$ 。递归分支顺序执行，沿调用链同时保留的数组规模呈几何递减，所以不是 $O(n\log n)$ 的同时占用空间。最终输出仅含平方值与两个编号，为 $O(1)$ 个数值对象。

易错点

只比较左右内部最短距离。 还必须检查跨分界线的点对。
条带内只检查纵向紧邻的一个点。 最近点不一定是纵坐标相邻点，要依据几何常数界检查候选。
按横坐标值而非位置划分。 横坐标相同可能导致一侧为空，破坏均衡甚至使递归不缩小。
平方值与未平方的坐标差混比。 代码中的距离、横差、纵差统一平方后比较。
排序后编号发生改变。 输出应携带输入时的编号，而不是排序后位置。
将两个同坐标输入去重。 本题允许它们形成距离0的合法点对，不能去重。

课堂练习

[(0,0),(1,0),(5,5)] 的返回结果是什么？
主示例只比较左右内部，会得到什么错误结果？
[(1,1),(1,1)] 是否能配对？其最短距离平方是多少？
为什么有两个递归调用，却不是 $O(n^2)$ ？为什么只有对数深度，又不是 $O(\log n)$ ？

参考答案

(1, (0,1))，两点横坐标差1、纵坐标差0。
返回 (13, (0,1))，漏掉跨侧点对 (1,2) 的平方距离1。
可以，它们输入编号不同；返回 (0, (0,1))。
两个子问题各只包含约一半的点，当前层工作为线性。每层总工作为 $O(n)$ ，有 $O(\log n)$ 层，所以总时间为 $O(n\log n)$ ；深度只描述一条调用链，不能代替全部分支的工作量。