如何选择复盖另一个圆的最小圆集？

Question

我正在寻找一些解决方案，如果给定一组具有2D中心点和半径的圆，则在s中返回一个最小子集m，该子集完全覆盖具有2D中心点和半径的特定圆。最后一个圆圈不在s中。

我已经选择了圆形，但如果我们把它们改成正方形、六边形等也没关系。

Answer 1

你有两个截然不同的问题：你需要把几何问题变成组合问题，然后你需要解决组合问题。对于后者，你正在研究一个最小集合覆盖问题，应该有很多关于它的文献。就我个人而言，我喜欢Knuth的舞蹈链接方法来列举一个集合覆盖的所有解决方案，但我想对于一个最小的解决方案，你可以做得更好。CPLEX公式（与您的标记匹配）将为每一行使用二进制变量，为每列使用≥1个约束。

现在，关于将几何学转化为组合学。你所有的圆圈的所有线条把平面分成一堆区域。这些区域是用线划分的。特别相关的是两个或多个圆圈相交的点。这些点之间的直线的确切形状不太相关，你可以想象直接拉这些弧，得出一个更经典的平面图表示。计算所有圆之间的成对交点。按角度排序单个圆的所有交点，并按该顺序将它们与图边相连。对所有圈子都这样做。然后，您可以做一种桶填充，以确定每个圆中哪些图形面在内部，哪些面在外部。

现在，您有了设置覆盖的矩阵：大圆内的每个图形面都是您需要覆盖的列。每一个圆都是一排，并且覆盖了其中的一些面，你知道哪一个。