3+维度中最接近的一对(分而治之)

Question

我正在努力解决分裂和征服算法如何适用于大于2的维度,特别是如何在两个子问题之间找到最接近的点对.

我知道我只需要考虑轴上d两者之间距离的距离x.

我知道在3d情况下,我需要将每个点与仅15个其他点进行比较.

我不明白的是如何选择那15分.在第二种情况下,只需按值对值进行排序,y然后按顺序进行排序.但是,在3d情况下,需要将每个点y 与 z轴和轴上最接近它的15个点进行比较.我似乎无法找到一种方法来确定那些15点是什么样的,没有最坏的情况O(n^2)......

我在这里错过了什么？

Answer 1

一个简单的解决方案是创建一个包含所有点的八叉树或 kd 树，然后使用它来查找每个点的最近点。对于平均情况，即 O(N*log N)。

考虑到以下想法，可以实现平均情况下 O(N) 的更快解决方案：

如果将空间分成两半（例如通过某个轴对齐的平面），则会将点分为两个子集 A 和 B，并且两个最近的点可以都在 A 中，都在 B 中，或者一个在 A 中，一个在 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）重复。

此外，当这对盒子内的点数低于某个阈值时，您可以使用强力来找到最近的点对。

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