给定两个(大)点集,我如何有效地找到彼此最近的对？

Question

我需要解决一个计算问题,归结为搜索两组之间相互最近的点对.问题是这样的:

给定欧几里德空间中的一组点A和一组点B,找到所有对(a,b)使得b是B中与a的最近点,并且a是A到b中的最近点.

A组和B组的大小大致相等,我们将这个大小称为N.对于我的特殊问题,N大约为250,000.

蛮力解决方案是将每个点与每个其他点进行比较,其具有二次时间复杂度.有没有更有效的算法来做到这一点？

Answer 1

我发现在必须进行最近邻搜索时非常有用的数据结构是k -d树.维基百科有一个很好的概述,如果你正在实现自己的,这是对算法的一个非常深入的讨论(虽然一个库可能已经存在 - 你没有提到你正在使用的语言).关于k d树的最重要的事情是它允许在O(log N)时间内执行最近的neghbour搜索.

通过这种方式,您可以生成两个列表 - A中的成员及其在B中的最近邻居以及B中的成员及其在A中的最近邻居 - 在O(N log N)时间内.然后,您可以比较列表以查看哪些对匹配.天真地做,那是O(N ^ 2),尽管你可能想到一种更快的方法.

[编辑]你让我思考; 这是我的第二个念头:

for(a in A)
    b := nearest(B, a)
    if a = nearest(A, b)
        add (a, b) to results
    end if
end for

function nearest(X, y)
    return nearest member of set X to point y
end function

据我估算,这是O(N log N).