algorithm - 找到一个点，使得到一组点 P 中任何点的最大距离最小

Question

给定二维空间 P 中的一组点，其中 Pi = (Xi, Yi)，

我需要找到一个目标点 T 使得到任何 Pi 的最大距离最小化。

T不需要存在于P中，可以任意定义

有没有我可以使用的算法？

score 8 · Accepted Answer

8

于 2012-05-24T15:03:50.083 回答

score 1 · Accepted Answer

认为这可能是解决您的问题的一个很好的解释，但它是 O(n^2)

score 0 · Accepted Answer

我还没有证明这一点，但我认为解决方案只是：

(min(Xi) + max(Xi)) / 2, (min(Yi) + max(Yi))/2)

3 回答 3