我很难理解分治算法在大于二维时如何工作，特别是如何在两个子问题之间找到最近的点对。
我知道只需要考虑距离两者在x轴上的分割线上距离小于d的点。
我知道在三维情况下需要将每个点与其他15个点进行比较。
我不明白的是如何选择这15个点。在二维情况下，只需按y值对值进行排序并按顺序处理即可。然而，在三维情况下，每个点都需要与其在y和z轴上最接近的15个点进行比较。我似乎找不到确定这些15个点的方法，使其不具有O(n^2)的最坏情况复杂度...
我在这里缺少什么？
三维及以上维度中最接近的点对（分治算法）
7
- DonGato
1个回答
0
一个简单的解决方案是创建一个八叉树或k-d树，将所有点放入其中，然后使用它来查找每个点的最近点。这对于平均情况是O(N*log N)。
我认为更快的解决方案是平均情况下的O(N)，可以考虑以下思路：
如果你将空间分成两半（比如说通过某个轴对齐的平面），你会得到被分成两个子集A和B的点，而两个最近的点可以在A中，也可以在B中，或者一个在A中，一个在B中。
因此，您必须创建一个由3D框对组成的队列，按照它们之间的最小距离排序，然后：
1）从队列中选择第一对框
2）如果两个框都是同一个框A，则将其分成两个框B和C，并将对(B,B)、(C,C)和(B,C)推入队列中。
3）如果它们不同(A,B)，则将最大的框（例如B）分成两个框C和D，并将对(A,C)和(A,D)推入队列中。
4）重复以上步骤。
此外，当框内的点数低于某个阈值时，您可以使用暴力方法来查找最近的点对。
如果顶部的一对框之间的距离大于迄今为止发现的最小距离，则搜索停止。
我认为更快的解决方案是平均情况下的O(N)，可以考虑以下思路：
如果你将空间分成两半（比如说通过某个轴对齐的平面），你会得到被分成两个子集A和B的点，而两个最近的点可以在A中，也可以在B中，或者一个在A中，一个在B中。
因此，您必须创建一个由3D框对组成的队列，按照它们之间的最小距离排序，然后：
1）从队列中选择第一对框
2）如果两个框都是同一个框A，则将其分成两个框B和C，并将对(B,B)、(C,C)和(B,C)推入队列中。
3）如果它们不同(A,B)，则将最大的框（例如B）分成两个框C和D，并将对(A,C)和(A,D)推入队列中。
4）重复以上步骤。
此外，当框内的点数低于某个阈值时，您可以使用暴力方法来查找最近的点对。
如果顶部的一对框之间的距离大于迄今为止发现的最小距离，则搜索停止。
- salva
2
1你所描述的O(n)算法叫什么名字？该算法是否有参考链接？ - Mahmudur Rahman
3那个算法的名字是“它不存在”。可以证明，在最坏情况下，最优的基于比较的最近点对问题算法速度不会比O(n*log(n))更快。 - facetus
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接