algorithm - 给定两组(大)点，我如何有效地找到彼此最近的点对？

Question

我需要解决一个计算问题，该问题归结为在两个集合之间搜索相互最近的点对。问题是这样的:

给定欧氏空间中的一组点 A 和一组点 B，找到所有对 (a,b) 使得 b 是 B 中距离 a 最近的点，a 是 A 中距离 b 最近的点。

集合 A 和 B 的大小大致相等，我们称这个大小为 N。对于我的特定问题，N 大约为 250,000。

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

Answer 1

当我必须进行最近邻搜索时，我发现一个非常有用的数据结构是 kd 树。 Wikipedia有一个很好的概述和this如果您要实现自己的算法(尽管可能已经存在一个库 - 您没有提及您使用的是哪种语言)，则该算法是一个很好的深入讨论。 kd 树最重要的一点是它允许在 O(log N) 时间内执行最近邻搜索。

这样，您可以在 O(N log N) 时间内生成两个列表 - A 的成员及其在 B 中的最近邻居以及 B 的成员及其在 A 中的最近邻居。然后，您可以比较列表以查看哪些对匹配。天真地完成，这是 O(N^2)，尽管您可能会想出一种更快的方法。

[edit] 你让我思考；这是我的第二个想法:

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)。