给定两个（大）点集，我如何有效地找到彼此最接近的点对？

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

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

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

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

当我必须进行最近邻搜索时，我发现一个非常有用的数据结构是k-d-tree。维基百科 http://en.wikipedia.org/wiki/Kd-tree有一个很好的概述和如果您正在实现自己的算法，那么这是对算法的出色深入讨论（尽管库很可能已经存在 - 您没有提及您正在使用哪种语言）。 kd 树最重要的一点是它允许在 O(log N) 时间内执行最近邻搜索。

这样，您可以在 O(N log N) 时间内生成两个列表：A 的成员及其在 B 中的最近邻居以及 B 的成员及其在 A 中的最近邻居。然后，您可以比较列表以查看哪些对匹配。如果天真地这样做，那就是 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)。