3+维度中最接近的点对（分而治之）

Question

我正在纠结于分治算法对于大于2的维度是如何工作的，特别是如何在两个子问题之间找到最接近的点对。

我知道在3D的情况下，我需要将每个点与其他15个点进行比较。

我不明白的是，那15点怎么选？在2D情况下，只需按y值对值进行排序，然后按顺序进行遍历。然而，在3D情况下，每个点都需要与y和z轴上离它最近的15个点进行比较。我似乎找不到一种方法来确定这15个点是什么，而且不存在O(n^2)...

我错过了什么？

Answer 1

一个简单的解决方案是创建一个八叉树或一个k-d树，包含所有的点，然后用它为每个点找到最近的点。对于平均情况是O(N*logn)。

一个我认为对于平均情况是O(N)的更快的解决方案可以考虑以下想法来实现：

如果你将空间分割成两半（比如通过某个轴对齐的平面），你会得到两个子集A和B中的点，最近的两个点可以都在A中，也可以都在B中，或者一个在A中，一个在B中。

1）从队列中选择第一对框

2）如果两个方框都是同一个方框A，则将其在两个方框B和C中对半，并将成对(B，B)，(C，C)和(B，C)推入队列。

3）如果它们是不同的（A,B）,将最大的（例如,B）分成两半获得框C和D,并将成对的（A,C）和（A,D）推入队列。

此外，当一对方框内的点数低于某个阈值时，您可以使用蛮力来找到最近的一对点数。

一旦顶部对中的两个框之间的距离大于到目前为止找到的最小距离，搜索就会停止。