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

Question

我正在寻找一些解决方案，给定一组S具有2D圆心点和半径的圆，返回M中的最小子集M，该子集完全覆盖具有2D圆心点和半径的特定圆。最后一个圆不在S中。你知道吗

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

Answer 1

你有两个截然不同的问题：你需要把几何问题变成一个组合问题，然后你需要解决这个组合问题。对于后者，您将看到一个minimum set cover problem，应该有大量关于这个的文献。就我个人而言，我喜欢Knuth的Dancing Links方法来枚举集合覆盖的所有解，但是我想对于一个最小解你可以做得更好。CPLEX公式（与您的标记匹配）将为每一行使用一个二进制变量，为每一列使用一个≥1的约束。你知道吗

现在我们来谈谈把几何变成组合数学。所有圆的线把平面分成一堆区域。这些区域用线隔开。特别相关的是两个或多个圆相交的点。这些点之间的直线的确切形状不太相关，您可以想象将这些弧拉直以得到更经典的平面图表示。所以计算所有圆之间的成对交点。对单个圆by angle的所有交点进行排序，并按顺序将它们与图边连接起来。对所有圈子都这样做。然后，您可以执行一种桶填充来确定每个圆的哪些图形面在内部，哪些图形面在外部。你知道吗

现在你有了覆盖集合的矩阵：大圆内的每个图面都是你需要覆盖的一列。每个圆都是一排，覆盖了其中的一些面，你知道是哪个面。你知道吗