我正在努力理解分而治之算法如何在大于 2 的维度上工作，特别是如何找到两个子问题之间最接近的点对。
我知道我只需要考虑
dx我知道在 3d 情况下，我只需将每个点与其他 15 个点进行比较。
我不明白的是如何选择这15个点。在 2d 情况下，只需按
yyzO(n^2)我在这里缺少什么？
一个简单的解决方案是创建一个包含所有点的八叉树或 k-d 树，然后用它来查找每个点的最近点。对于平均情况来说，这是 O(N*log N)。
我认为平均情况下的更快解决方案是 O(N)，可以考虑以下想法来实现：
如果将空间分成两半（比如通过某个轴对齐的平面），您会得到分为两个子集 A 和 B 的点，并且两个最近的点可以同时在 A 中，都在 B 中，或者一个在 A 中，一个在 A 中，一个在 A 中，一个在 A 中，一个在 A 中，一个在 A 中，一个在 A 中，一个在 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) 重复。
此外，当这对盒子内的点数低于某个阈值时，您可以使用蛮力来找到最近的点对。
一旦顶部对中的两个框之间的距离大于迄今为止找到的最小距离，搜索就会停止。
对于3D最近点算法中的少量点，进行强力搜索。否则，将点分为前半部分和后半部分，并递归求解以找到每个点中最近的距离 一半。现在我们只需要检查从中平面的一半到另一半的点。然而，我们只需要担心靠近这个中平面的区域，因此我们最终关心的是二维平面附近的点。因此，我们使用类似于二维（平面）中最近点算法的方法来处理这条带：我们将靠近平面的点分为左半部分和右半部分，并在每个中递归求解 一半。然后我们只需要关注靠近分割中平面的点，所以我们最终得到一个长而窄的长方体关注区域，有点像一维线，所以我们使用类似于一维线的方法D 线上点的情况（对点进行排序并从每个点到接下来的几个点进行检查）。 在 3d 点算法中，从中点开始检查的点数为 31。（检查较少的点可能是可以的，但 31 是最容易证明合理的。）Yδ 包含高长方体中的点，其横截面为2δ × 2δ 的平方，被 xmid 和 zmid 平分。现在，如果我们想象将这个长方体分解成边长为 δ/2 的小立方体，如果立方体中有两个点，它们的距离将小于 δ。请注意，每个立方体完全位于左/前象限、左/后象限、右/前象限或右/后象限。我们知道有2个点都在左边，或者都在右边，或者都在后面，或者都在前面，其距离大于或等于δ。这给我们带来了矛盾，所以每个立方体中最多只能有一个点。
致谢：Shelby Kimmel（米德尔伯里学院计算机科学教授）