algorithm - 求 d 维空间中一组 n 个点的直径

Question

我很感兴趣的是在 128 维中找到两个点集的直径。第一个有 10000 个点，第二个有 1000000 个点。出于这个原因，我想做一些比采用 O(n²) 的天真方法更好的事情。该算法将能够处理任意数量的点和维度，但我目前对这两个特定数据集非常感兴趣。

我对提高速度而非准确性非常感兴趣，因此，基于 this ，我会找到点集的(近似)边界框，通过计算每个坐标的最小值和最大值，因此 O(n*d) 时间。然后，如果我找到这个盒子的直径，问题就解决了。

在 3d 的情况下，我可以找到一侧的直径，因为我知道两条边，然后我可以在垂直于这一侧的另一侧应用勾股定理。然而，我不确定这一点，而且可以肯定的是，我看不出如何将它推广到 d 维。

---

可以找到一个有趣的答案here ，但它似乎特定于 3 个维度，我想要一个 d 维度的方法。

有趣的论文:关于计算高维欧氏空间中点集的直径。 Link .但是，在这个阶段，实现该算法对我来说似乎太过分了。

Answer 1

该问题的经典 2-approximation 算法，运行时间为 O(nd)，是选择任意一个点，然后返回到另一个点的最大距离。直径不小于该值且不大于该值的两倍。