2组点的最大距离与2因子近似值

Question

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

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

Answer 1

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

你可以在O(k.log(k))中计算出凸壳。

https：/docs.scipy.orgdocscipyreferencegeneratedscipy.spatial.ConvexHull.html。

之后，你只需要测试边界上的点。

这是确定性的方法，你可以应用启发式、随机化搜索来做得更快，但它们不能保证提供正确的解决方案。

这里有一篇论文，用另一种算法讨论了这个问题。https: /arxiv.orgftparxivpapers17081708.02758.pdf。