最近点对问题

算法

最近点对问题是在二维平面上找到距离最近的两个点。分治算法通过将点集按x坐标排序,递归地在左右两半部分寻找最近点对,最后考虑跨越中线的点对。

时间复杂度:最佳 O(n log n) | 最差 O(n log n)
空间复杂度:O(n)

算法讲解

最近点对问题

介绍

最近点对问题(Closest Pair of Points Problem)是计算几何学中的一个经典问题:给定平面上的n个点,找出其中的一对点,使得它们之间的距离最小。这个问题看似简单,暴力解法可以通过计算所有点对的距离在O(n²)时间内解决,但使用分治策略可以将时间复杂度优化至O(n log n)。该问题在空间索引、聚类分析、碰撞检测等领域有广泛应用。

算法步骤

分治法解决最近点对问题的关键步骤如下:

  1. 分解:
    • 将所有点按照x坐标排序
    • 找到中间点,将点集分为左右两部分
  2. 解决:
    • 递归求解左半部分的最近点对,距离记为δ₁
    • 递归求解右半部分的最近点对,距离记为δ₂
    • 取δ = min(δ₁, δ₂)
  3. 合并:
    • 考虑跨越中线的点对,即一个点在左半部分,一个点在右半部分
    • 只需考虑中线左右各δ距离内的点
    • 对这些点按y坐标排序,对每个点只需与其后最多6个点比较距离
    • 更新最小距离

...