线段集的最小面积几何覆盖

Question

我试图解决的问题是：

给定平面上可以以圆为中心的M个点的集合和N个需要被圆覆盖的线段的集合，求线段的最小面积圆覆盖。也就是说，求圆和中心（从M个点中选择）的半径，使得所有N条线段都被覆盖，圆的总面积最小化。

任何指向论文、代码或近似算法的指针都会很棒。

Answer 1

编辑：刚刚意识到原来的方法（移到最后）可能没有覆盖一条线段最好被多个圆很好地覆盖的情况。所以我 ；认为最好迭代点，而不是线段，在圆边界处向下切割线段：

1. 找到“最差”点，即其最佳圆中心选项与相应线段至少部分在圆内需要最大附加圆面积的点。构造/扩展相应的圆。
2. 从集合中删除完全覆盖的线段，并在圆边界处切割部分覆盖的线段。
3. 循环直到不再保留线段。

主要思想是在任何情况下都要做必要的事情。重叠的圆圈是如何计算的？ 在后面的迭代中回到第一步时，某种成本启发式可能会改善结果。

1. 找到“最差”线段，即任何圆心选项需要最大圆的线段，并构造相应的圆。
2. 从集合中删除覆盖的线段。
3. 循环直到不再保留线段。