点集最近点对

概述[编辑 | 编辑源代码]

最近点对问题（Closest Pair of Points Problem）是计算几何中的基础问题之一：给定平面上的 $n$ 个点，找出其中欧几里得距离最小的两个点。该问题在碰撞检测、地理信息系统（GIS）和模式识别等领域有广泛应用。

问题定义[编辑 | 编辑源代码]

给定点集 $P = {p_{1}, p_{2}, \dots, p_{n}}$ ，其中每个点 $p_{i} = (x_{i}, y_{i})$ ，求解： $\min_{1 \leq i < j \leq n} \sqrt{(x_{i} - x_{j})^{2} + (y_{i} - y_{j})^{2}}$

暴力解法[编辑 | 编辑源代码]

最直接的方法是计算所有点对的距离并取最小值。

算法步骤[编辑 | 编辑源代码]

1. 遍历所有 $(\binom{n}{2})$ 个点对。 2. 计算每对点的欧几里得距离。 3. 记录最小距离及其对应的点对。

代码示例[编辑 | 编辑源代码]

  
import math  

def brute_force_closest_pair(points):  
    min_dist = float('inf')  
    pair = None  
    n = len(points)  
    for i in range(n):  
        for j in range(i + 1, n):  
            dist = math.sqrt((points[i][0] - points[j][0])**2 + (points[i][1] - points[j][1])**2)  
            if dist < min_dist:  
                min_dist = dist  
                pair = (points[i], points[j])  
    return pair, min_dist  

# 示例输入  
points = [(2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4)]  
print(brute_force_closest_pair(points))

输出：

(((2, 3), (3, 4)), 1.4142135623730951)

复杂度分析：时间复杂度为 $O (n^{2})$ ，空间复杂度为 $O (1)$ 。

分治法优化[编辑 | 编辑源代码]

分治法可将时间复杂度优化至 $O (n \log n)$ ，步骤如下： 1. 按x坐标排序点集并递归分割为左右两半。 2. 递归求解左右两半的最近点对。 3. 合并阶段：检查距离分割线小于当前最小距离的点，构成候选点对。

算法细节[编辑 | 编辑源代码]

分割线：取点集的中位数x坐标。
候选区域：仅需检查距离分割线 $d$ （当前最小距离）以内的点。
纵坐标优化：在候选区域内按y坐标排序，只需检查后续7个点。

代码示例[编辑 | 编辑源代码]

  
def closest_pair(points):  
    points_sorted_x = sorted(points, key=lambda x: x[0])  
    return _closest_pair(points_sorted_x)  

def _closest_pair(points):  
    n = len(points)  
    if n <= 3:  
        return brute_force_closest_pair(points)  

    mid = n // 2  
    left_pair, left_dist = _closest_pair(points[:mid])  
    right_pair, right_dist = _closest_pair(points[mid:])  
    min_dist = min(left_dist, right_dist)  
    min_pair = left_pair if left_dist < right_dist else right_pair  

    # 合并阶段  
    mid_x = points[mid][0]  
    candidates = [p for p in points if abs(p[0] - mid_x) < min_dist]  
    candidates.sort(key=lambda x: x[1])  

    for i in range(len(candidates)):  
        for j in range(i + 1, min(i + 8, len(candidates))):  
            dist = math.sqrt((candidates[i][0] - candidates[j][0])**2 + (candidates[i][1] - candidates[j][1])**2)  
            if dist < min_dist:  
                min_dist = dist  
                min_pair = (candidates[i], candidates[j])  
    return min_pair, min_dist