用圆圈找到一组点的封面

Question

在由坐标和数字K(0 <K <N)给出的集合V中有N个点.我需要确定具有相同半径R的K个圆(磁盘),它们的中心位于V set中的点.这些圆圈必须"覆盖"所有N个点,R是最小的.

谁能帮我这个？

Answer 1

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

最后得到的半径R是从最后一个点到下一个最远点的距离.通过构造,您可以保证覆盖半径为中心的每个k点的所有点,并且通过三角不等式,该R在最佳半径的2倍内.

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

请记住,三角形不等式成立,并且在我们的溶液中,所有点都包含在半径为R的$ k $球中.请注意,所选的$ k + 1 $点至少与所有其他点的距离为R. 假设OPT不同,并使用半径小于R/2的球.我们的溶质中没有两个k + 1点(k个中心+ 1个点)可以位于同一个OPT簇内,因为每对点都是> = R,所以两者都在一个R/2球内OPT的单一中心由tri.ineq.因此,OPT的每个球最多可以包含我们的溶液的一个中心,并且OPT需要k + 1个球.矛盾. (2认同)

Answer 2

您描述的问题是一个更一般的优化问题（称为覆盖问题）的一个实例，可以通过线性规划松弛来解决。您也许能够定义一个成本函数，该函数与圆的半径R（例如所有圆的半径之和）以及选择绘制圆的点的指示符变量呈线性。该成本函数的定义会受到约束，迫使圆圈覆盖集合中的所有点（请查看有关LP的维基百科文章以获取示例）

定义成本函数和约束后，您可以使用多个求解器（其中许多是免费的）来求解优化问题。