给定两组（大量）点，如何高效地找到彼此最近的点对？

Question

我需要解决一个计算问题，即在两个点集之间搜索相互最近的点对。该问题大致如下：

给定欧几里得空间中点集A和点集B，找到所有满足条件（a，b）的点对，其中b是B中距离a最近的点，而a是A中距离b最近的点。

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

暴力解决方案是将每个点与其他每个点进行比较，这具有二次时间复杂度。 是否有更有效的算法来解决这个问题呢？

- Ryan Thompson

---

这真的取决于你的数据是如何保存/组织的。我建议查看这个维基页面http://en.wikipedia.org/wiki/Kd-tree以获取一些想法。这可能会给你一个更有效的搜索，但也可能需要重新格式化你的数据点。 - TZHX

这是一个纯技术问题，应该发布在 StackOverflow 上。 - Péter Török

我支持 @Peter 的观点，这是一个具体的问题，因此应该在 SO 上发布。 - Gaurav

Answer 1

我在进行最近邻搜索时发现的一种非常有用的数据结构是 k-d 树。Wikipedia提供了一个很好的概述，而this则是一个非常深入的算法讨论，如果你想要自己实现（虽然可能已经存在一个库——你没有提到你使用的编程语言），那么这个链接可能会帮助到你。关于 k-d 树最重要的事情是它允许在 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) 的时间复杂度。

- Scott

---

我正在使用R语言，而R确实没有一个通过kd树寻找最近邻的包。它只有一个用于计算两组点之间最近邻的包。http://cran.r-project.org/web/packages/RANN/RANN.pdf - Ryan C. Thompson

使用列表合并可以在O(N)时间内将最近邻居的两个列表合并起来：只需交换每对B的最近邻居中元素的顺序，按其第一个元素进行排序，并从两个列表的开头开始向下遍历，找到同时存在于两个列表中的元素，并将它们写入输出列表。 - j_random_hacker

Answer 2

很抱歉挑起了一个比较旧的话题，但我只是想添加一个我在算法设计课程教材中找到的解决方案：

可以使用分治（类似于归并排序）方法解决此问题，时间复杂度应该为O(n logn)，我只看过用于在一组点内查找最短距离的情况，但应该很容易适应需要每个匹配对由来自不同集合的点组成的情况。

1. 按X值对所有点进行排序。
2. 将整个集合分成两个相等的部分。
3. 对每个部分进行递归，并选择两个中的最小距离(d)。
4. 找到左半部分中最右侧的点(p)，并检查p_x和p_x + d之间所有点的距离，如果其中任何距离都比d短，则返回该d作为结果，否则返回d。

- Hobblin

---

回到这个答案，如何使它适用于例如三维情况？ - Jean-Yves

我认为如果你不断地在迭代中切换轴（先按X排序和分割，然后按Y排序和分割，...再次按X排序和分割），最终会得到一个经典的BSP树。 - 9000

Answer 3

• BSP / Octree / Kd-tree（感谢，TZHX）
• 空间填充曲线（例如使用希尔伯特曲线）；谷歌可以得到许多相关结果以进行配对查找。

- 9000

---

我认为这个答案中有一些指向潜在解决方案的好的指针。它并不是一个完全构思完备的答案，这可能反映了这个问题的真实性质——我不知道是否存在一个简单的答案，也不确定迄今为止发布的其他答案是否好。 - Bill

@Bill 我认为有关_k_-d树的被接受答案很好。这种方法已经被广泛理解和使用，因此找到参考实现或帮助很容易。空间填充曲线更加复杂；如果空间分割解决方案看起来不好，我已将它们添加为研究的起点。 - 9000

抱歉，我误解了问题。我以为是要找到所有点之间平均距离最小的配对（而不仅仅是彼此最近的子集）。这是一个不同且更困难的问题。 - Bill

Answer 4

虽然这是一个旧帖子，但我看到有一个相当新的评论。

我认为对于一个n维点集，两个集合之间的近点可以通过找到集合差的原点附近点来找到。您可以查找贝尔实验室的菲利普·沃尔夫（Phillip Wolfe）的论文，其中他阐述了该算法。您可以考虑从集合A中取一个随机点，找到集合B中最近的点，然后找到与集合B中该点最近的点，以此类推。 http://link.springer.com/article/10.1007%2FBF01580381

- Mechenix