python - 2 因子近似的 2 组点的最大距离

Question

给定一组 n 个点，我随机取 k 个点。我需要以最有效的方式计算k点与n点的最大距离，系数为 2 近似（以某种方式利用三角不等式）。我的第一个想法是使用曼哈顿距离而不是欧几里得距离，但这并没有降低复杂性，因为它仍然是O(n*k)。可能有什么想法？

编辑：如果我首先计算 k 个点中的 2 个最远点，然后计算 2 个点与所有 n 个点的距离怎么办？

标签： pythontime-complexityapproximationpairwise-distance

Answer 1

从技术上讲，如果您只寻找距离最大的点，您可以用这些点构建一个多边形（凸包），最大距离应该是边界中的那些。

您可以在 O(k.log(k)) 中计算凸包

https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.ConvexHull.html

之后，您只需在边界上测试点。

这是确定性方法，您可以应用启发式随机搜索来更快地完成它，但不能保证提供正确的解决方案。

这是一篇用另一种算法讨论该主题的论文：https ://arxiv.org/ftp/arxiv/papers/1708/1708.02758.pdf