用不同半徑的圓覆蓋多邊形

Question

我有一個封閉的多邊形，我想用一組不同半徑的K個圓來完全覆蓋它，這樣圓形覆蓋的區域在多邊形之外是最小的。這似乎是線性編程的理想候選者。有人知道這個問題的標準公式/算法嗎？

Answer 1

你可以看看Smallest-circle problem，這相當於你的問題K = 1。

在上面的Wiki頁面中，據說存在線性算法。然而，在loc中描述的算法。 CIT。 Nimrod Megiddo的論文很複雜。所以我的感覺是，你可能能夠用線性規劃陳述你的問題，但找到最好的算法將是遠遠不明顯的。