以下问题： 给定是一个任意多边形。应以给定半径的最小圆数覆盖 100%。
注意： 1）自然圆圈必须重叠。2）我尝试解决任意多边形的问题。但也赞赏 CONVEX 多边形的解决方案。3）据我所知，这个问题是 NP-hard（一种为 Set-cover 问题找到最小尺寸集覆盖的算法）选择：U = 多边形和 S1...Sk = 具有任意中心的圆。
我的解决方案： 我已经阅读了一些论文并自己尝试了一些事情。我想出的最有前途的想法实际上已经在Covering an absolute area with circles of equal radius 中指出过。
所以我想我最好尽快尝试描述我自己的想法，然后完善我的问题。
这张照片已经让你对我的工作有了一个很好的了解
IDEA 和问题公式 1. 我用它们对应的六边形来近似圆，并对整个 R2 进行细分，即一个足够大的区域；关键字六边形最接近的包装。（青色...镶嵌，红色虚线，青色六边形的中心） 2. 我把多边形放在这个镶嵌区域中间的某个地方，并计算覆盖多边形所需的六边形的数量。
在下文中，我试图通过逐步移动多边形来最小化 N，这是覆盖多边形所需的六边形数量，在每一步“计数”N 之后。
解决问题： 这就是困难的时候（对我来说）。我不知道有任何优化器可以正确解决这个问题，因为它们都会在稍微移动多边形并且没有观察到任何变化后终止。
我的解决方案如下： 首先注意这是一个周期性问题： 1. 多边形可以在水平方向 x 上移动，周期为六边形的 3*r（边长 = 半径 r）。2.多边形可以在垂直方向y上移动，周期为六边形的r^2+r^2-2*r r cos(2/3*pi)。3. 多边形可以以 2/3*pi 的周期旋转 phi。
这意味着，必须搜索可能解决方案的有限区域才能找到最佳解决方案。所以我所做的是，我为 (x,y,phi) 选择一个步长，然后简单地蛮力计算所有可能的解决方案，选出最优的。
细化我的问题 1) 问题的表述是否明智？现在我正在研究一种只对非常小的区域进行细分的算法，因此必须计算尽可能少的六边形。2）有没有更智能的优化器来解决这个问题？3）最后：我也很难找到合适的文献，因为我不知道我不知道要寻找的正确关键字。所以如果有人能给我提供文学作品，那也将不胜感激。
实际上，我可以继续讨论我尝试过的其他事情，但我认为你们中没有人愿意花整个下午来阅读我的问题。
提前感谢所有花时间思考的人。
垫
PS我在matlab中实现我的算法