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

Question

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

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

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

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

Answer 1

当我必须进行最近邻搜索时，我发现一个非常有用的数据结构是k-d-tree。 Wikipedia 有很好的概述，这是一个很好的深入讨论如果您正在实现自己的算法（尽管很可能已经存在一个库 - 您没有提及您正在使用哪种语言）。 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)。

Answer 2

抱歉，我选择了一个相当旧的线程，但我只是想添加一个我在算法设计课教科书中找到的解决方案：

有一种分而治之（想想合并排序）的方法来解决这个问题，应该是O(n logn)，我只看到它用于查找一组点内的最短距离，但它应该很容易适应要求每个配对由来自不同集合的点组成。

1. 根据 X 值对所有点进行排序。
2. 将整个集合分成两等份。
3. 在每一半上递归并选择两者的最小距离 (d)
4. 找到左半部分最右边的点 (p) 并检查之间所有点的距离p_x 和 p_x + d，如果其中任何一个距离短于 d（即要返回的 d），否则返回d。

Answer 3

• BSP / 八叉树 / Kd-tree (谢谢，TZHX）
• 空间填充曲线（例如使用希尔伯特曲线）； Google 生成许多相关结果 用于寻找配对。

Answer 4

老线程，但我看到有一个最近的评论。

我相信对于 n 维点集，可以通过查找到集合差值原点的近点来找到两个集合之间的近点。您可以查找贝尔实验室的 Phillip Wolfe 撰写的论文，他在其中阐述了该算法。你可以这样想：在集合 A 中取一个随机点，在集合 B 中找到最近的点，然后在集合 B 中找到距离该点最近的点，依此类推。 http://link.springer.com/article/10.1007%2FBF01580381