具有给定直径的最小圆数的覆盖多边形

Question

以下问题：给出的是任意多边形。它应以给定半径的最小圆数100%覆盖。

注： 1)自然圆必须重叠。2)我试图解决任意多边形的问题。但是，凸多边形的解也是值得赞赏的。3)据我所知，这个问题是NP-硬( an algorithm to find the minimum size set cover for the Set-cover problem )选择:U=多边形，S1...Sk =任意中心的圆。

我的解决方案：我已经读过一些论文，并且自己尝试了一些东西。我想出的最有希望的想法其实已经在Covering an arbitrary area with circles of equal radius中提到了。

所以我想我最好尽快描述我自己的想法，然后再改进我的问题。

这张照片已经让你对我的工作有了一个很好的了解。

​

​

思想和问题公式 1.我用它们对应的六边形近似圆，并将整个R2 (即足够大的区域；关键字六边形最接近的封装)与之相结合。(青…)2.我把多边形放置在这个网格区域的中间，并计算出覆盖多边形所需的六边形数量。

在下面，我试图最小化N，即覆盖多边形所需的六边形数，方法是在每一步“计数”N之后，一步一步地移动多边形。

解决了这个问题：，所以当它变得困难时(对我来说)。我不知道任何适当解决这个问题的优化器，因为它们都是在移动多边形之后终止的，并且没有观察到任何变化。

我的解是：首先注意到这是一个周期问题: 1.多边形可以在六边形的周期为3*r (边长=半径r)的水平方向上移动。2.多边形可向垂直方向y移动，周期为r^2+r^2-2*r_r_cos(2/3*pi)。3.多边形可以在周期为2/3*pi的情况下旋转。

这意味着，我们必须搜索有限区域的可能解，以找到最优解。所以我所做的就是，为(x，y，phi)选择一个步长，简单地用蛮力计算所有可能的解，选出最优解。

澄清我的问题 1)这个问题是聪明地表述出来的吗？现在，我正在研究一种算法，该算法只计算一个很小的区域，这样就必须计算出尽可能少的六边形。( 2)是否有一个更智能的优化器来解决这个问题? 3)最后:我也很难找到合适的文献，因为我不知道该找哪个关键词。所以如果有人能给我提供文学作品，我们也会非常感激的。

事实上，我可以继续做我尝试过的其他事情，但是我想你们中没有一个人想花一整个下午的时间来读我的问题。

提前通知每一个花时间思考的人。

垫子

PS I在matlab中实现我的算法

Answer 1

我喜欢你的做法！当您提到您的优化时，我认为一个很好的方法是旋转六边形网格，并将其转换，直到找到覆盖该区域的最少数量的圆圈。你不需要旋转360，因为图案是对称的，所以只有360/6。

我已经研究这个问题有一段时间了，并且刚刚发表了一篇包含解决这个问题的代码的论文！它采用遗传算法和BFGS优化方法。您可以在这里找到到该论文的链接：https://arxiv.org/abs/2003.04839

Answer 2

编辑：答案重写了(没有限制说圆圈不能离开多边形)。

您可能对Covering a simple polygon with circles感兴趣。我认为该算法可以工作，也可以扩展到复杂多边形。

Answer 3

1.在最小大小的矩形中题注给定的多边形2.按圆圈最优地覆盖该矩形(算法可用)