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

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²)复杂性高，对于较大的输入来说非常慢。我想找到一个更快，优化的解决方案，因此我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都会更远，不应予以考虑。

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

您肯定需要大量的动态编程来为大型集合提供合理的运行时间。