最近点对问题

最近点对问题（Closest Pair of Points Problem）是计算几何中的一个经典问题，其目标是在给定的平面点集中找到距离最近的两个点。该问题广泛应用于计算机图形学、地理信息系统（GIS）、碰撞检测等领域。本文将介绍分治算法在解决最近点对问题中的应用，并提供详细的实现与分析。

问题描述[编辑 | 编辑源代码]

给定平面上的 $n$ 个点 $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. 划分：将点集 $P$ 按 $x$ 坐标排序后，划分为左右两个子集 $P_{L}$ 和 $P_{R}$ ，各包含约一半的点。 2. 递归求解：分别计算 $P_{L}$ 和 $P_{R}$ 中的最近点对距离 $d_{L}$ 和 $d_{R}$ 。 3. 合并：取 $d = \min (d_{L}, d_{R})$ ，检查是否存在跨越左右子集的点对距离小于 $d$ 。

合并阶段的优化[编辑 | 编辑源代码]

合并时只需检查距离分割线（中垂线）不超过 $d$ 的带状区域内的点。将这些点按 $y$ 坐标排序后，只需比较每个点与其后续最多7个点的距离。

算法实现[编辑 | 编辑源代码]

以下是使用Python实现的分治算法：

import math

def closest_pair(points):
    # 预处理：按x坐标排序
    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(points)
    
    mid = n // 2
    mid_point = points[mid]
    
    # 递归处理左右子集
    dl = _closest_pair(points[:mid])
    dr = _closest_pair(points[mid:])
    d = min(dl, dr)
    
    # 收集距离分割线不超过d的点
    strip = [point for point in points if abs(point[0] - mid_point[0]) < d]
    strip_sorted_y = sorted(strip, key=lambda x: x[1])
    
    # 检查带状区域内的点对
    min_strip = d
    for i in range(len(strip_sorted_y)):
        j = i + 1
        while j < len(strip_sorted_y) and (strip_sorted_y[j][1] - strip_sorted_y[i][1]) < min_strip:
            dist = distance(strip_sorted_y[i], strip_sorted_y[j])
            if dist < min_strip:
                min_strip = dist
            j += 1
    
    return min(d, min_strip)

def brute_force(points):
    min_dist = float('inf')
    for i in range(len(points)):
        for j in range(i+1, len(points)):
            dist = distance(points[i], points[j])
            if dist < min_dist:
                min_dist = dist
    return min_dist

def distance(p1, p2):
    return math.sqrt((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2)

# 示例输入
points = [(2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4)]
print("最小距离:", closest_pair(points))

输入与输出示例[编辑 | 编辑源代码]

输入：[(2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4)] 输出：最小距离: 1.4142135623730951 解释：最近点对是(2, 3)和(3, 4)，其距离为 $\sqrt{(3 - 2)^{2} + (4 - 3)^{2}} = \sqrt{2} \approx 1.414$ 。