gsa*_*ras 5 algorithm computational-geometry
我对求 128 维中两个点集的直径很感兴趣。第一个有 10000 点，第二个有 1000000 点。出于这个原因，我想做一些比需要 O(n\xc2\xb2) 的天真的方法更好的事情。该算法将能够处理任意数量的点和维度，但我目前对这两个特定的数据集非常感兴趣。
\n\n我对获得速度而不是准确性非常感兴趣，因此，基于此，我将通过计算每个坐标的最小值和最大值来找到点集的（近似）边界框，从而获得 O(n*d) 时间。然后，如果我找到这个盒子的直径，问题就解决了。
\n\n在 3d 情况下，我可以找到一侧的直径，因为我知道两条边，然后，我可以在垂直于这一侧的另一侧应用毕达哥拉斯定理。但是我对此不确定，并且可以肯定的是，我不知道如何将其推广到 d 维度。
\n\n可以在这里找到一个有趣的答案，但它似乎特定于 3 维，我想要一种针对 d 维的方法。
\n\n有趣的论文：关于计算高维欧几里德空间中点集的直径。关联。然而，在这个阶段，实现该算法对我来说似乎太多了。
\n