小编Grz*_*icz的帖子

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

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