我正在努力思考分治算法如何适用于大于 2 的维度，特别是如何找到两个子问题之间最接近的点对。
我知道我只需要考虑轴上d两者之间的距离内的点。x
我知道在 3d 案例中，我需要将每个点与其他 15 个点进行比较。
我不明白的是如何选择这15个点。在 2d 情况下，只需按值对值进行排序y并按顺序遍历它们。y 然而，在 3d 情况下，每个点都需要与和 z轴上最接近它的 15 个点进行比较。我似乎无法找到一种方法来确定这 15 点是什么，而不会出现最坏的情况O(n^2)......
我在这里想念什么？
一个简单的解决方案是创建一个包含所有点的八叉树或 kd 树，然后使用它为每个点找到最近的点。对于平均情况，这是 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) 重复。
此外，当这对框内的点数低于某个阈值时，您可以使用蛮力找到最近的一对点。
一旦顶部对中的两个框之间的距离大于目前找到的最小距离，搜索就会停止。