algorithm - 平面上距离最小的所有最接近的点对

Question

我必须从给定的集合中找到平面上所有最接近的点对。

我已经成功实现了一个类似于此伪代码函数的朴素算法O(n²)，其中set是输入上所有点的列表，count 是输入上所有点的计数，它返回 dist 这是找到的最小距离，result 是具有该距离的所有点对的列表。

function naive(Points[] set, int count)
    result = []
    distance = INF

    for i=0 to count-1:
        for j=i+1 to count:
           newDistance = distance(set[i], set[j])
           if newDistance < distance:
              result = []
              result.append({set[i], set[j]})
           else if newDistance == distance:
              result.append({set[i], set[j]})

   return (dist, result)

该解决方案效果很好，但由于 O(n²) 复杂度较高，对于较大的输入来说速度非常慢。我想找到一个更快、优化的解决方案，因此我使用基于 this article 的递归分治算法实现了 O(n logn) 解决方案，这对于大多数输入都适用，但由于这种方法不会迭代所有点，因此在像这样的输入上会失败(对的顺序和对内点的顺序并不重要):

Input:
{A[0,0], B[1,0], C[1,1] D[0,1]}

Current (wrong) output:
{A[0,0], D[0,1]}, {B[1,0], C[1,1]}

Desired output:
{A[0,0], B[0,1]}, {A[0,0], D[0,1]}, {C[1,1], B[1,0]}, {C[1,1], D[1,0]}

而且由于它是递归的，对于较大的输入，堆栈很容易溢出。有什么更好的方法来解决这个问题？

谢谢

Answer 1

但是您不需要将所有内容与其他所有内容进行比较。对于任何给定的点对，想象它们位于长度为 d 的矩形[与坐标轴对齐的矩形]对角线上。

• 如果斜率为正:
  • 位于线 x = d 左侧的任何其他点都会更远，不应被考虑。
  • 位于线 y = d 下方的任何其他点都会更远，不应予以考虑。
• 如果斜率为负:
  • 位于线 x = d 右侧的任何其他点都会更远，不应予以考虑。
  • 位于线 y = d 下方的任何其他点都会更远，不应予以考虑。

可以想象类似的约束在每种情况下都会为您提供一个边界框，这应该有助于消除内部循环中要考虑的大部分点，除非您有一个特别密集的星座。

这里肯定需要大量动态编程才能为大型集合提供合理的运行时间。