时间戳

首页 > 解决方案 > 平面上所有距离最小的最近点对

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

问题描述

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

我已经成功实现了一个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]}

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

谢谢

标签： algorithmrecursionoptimization

解决方案

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

  • 如果斜率为正：
    • 位于线左侧的任何其他点将x = d更远，不应考虑。
    • 位于该线下方的任何其他点将y = d更远，不应考虑。
  • 如果斜率为负：
    • 位于该线右侧的任何其他点将x = d更远，不应考虑。
    • 位于该线下方的任何其他点将y = d更远，不应考虑。

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

你肯定需要相当多的动态编程来为大型集合提供合理的运行时间。

推荐阅读