用不同半径的圆覆盖多边形

Question

我有一个封闭的多边形，我想用一组不同半径的K个圆来完全覆盖它，这样圆形覆盖的区域在多边形之外是最小的。这似乎是线性编程的理想候选者。有人知道这个问题的标准公式/算法吗？

Answer 1

你可以看看Smallest-circle problem，这相当于你的问题K = 1。

在上面的Wiki页面中，据说存在线性算法。然而，在loc中描述的算法。 CIT。 Nimrod Megiddo的论文很复杂。所以我的感觉是，你可能能够用线性规划陈述你的问题，但找到最好的算法将是远远不明显的。