algorithm - 找到一组带圆圈的点的覆盖

Question

我在集合 V 中有 N 个点，由它们的坐标和数字 K (0 < K < N) 给出。我需要确定具有相同半径 R 的 K 个圆(圆盘)，它们的中心在 V 集中的点中。这些圆圈必须“覆盖”所有 N 个点，R 是可能的最小值。

谁能帮我解决这个问题？

Answer 1

这个问题被称为(离散)$k$ 中心问题，是聚类中的一个众所周知的问题。虽然问题通常是 NP 完全问题，但有一种非常简单的算法可以在任何度量(包括问题的隐含二维欧几里德距离)的最优解的因子 2 内生成一个解。这是由于冈萨雷斯，如下

1. 任意点
2. 找到最远的邻居
3. 找到离这两个点最远的点
4. 依此类推，直到你有k分。

最终得到的半径 R 是从最后一点到下一个最远点的距离。通过构造，您可以保证用以每个 k 点为中心的圆盘覆盖所有点，并且根据三角不等式，这个 R 在最佳半径的 2 倍之内。

如果你知道你在飞机上，你可以在理论上做得更好(包括在 n 和 k 的指数中获得时间多项式的精确算法)，但在实践中，上述算法可能是最简单的