最大覆盖问题

aimisiyou

在一块矩形区域（长为A、宽为B）布置信号塔，已知信号塔信号覆盖半径为r,求至少需要设置几座信号塔才能覆盖全区域？信号塔如何布置？
如图给出的是A=1000，B=1000，r=200，最少需要13座信号塔。
有没有相关算法？

kastin

圆的相交弦构成正多边形最合理，而平面正多边形镶嵌只有正三角形、正方形和正六边形三种。所以先把要覆盖的矩形区域进行多边形镶嵌划分，然后用圆覆盖。找出圆最少的那种就行。

aimisiyou

之前也想过把圆看成圆内接正方形，但得出的正方形个数比实际需要的圆个数要大。用正多边形（如正八边形），边上和中间分布的小缝隙又太分散。

aimisiyou

如果A=2.5r,B=1.5r，最少需要几个圆才能覆盖全区域？

mathe

https://www2.stetson.edu/~efriedma/circovsqu/

aimisiyou

mathe 发表于 2020-2-27 16:44
https://www2.stetson.edu/~efriedma/circovsqu/

谢谢提供参考！我自己琢磨的7个圆的情况与参考图相似，但参考图覆盖的是正方形，其实覆盖的最大矩形(非正方形)面积为14.08138074。其左上角夹角为sin(2a)+sin(a)取最大值时的弧度值。

happysxyf

此类问题，是否有一般的解决公式，计算出圆的的个数？
s = 4.943+由Kari Nurmela和PatricÖstergård在2000年发现。边径比1000/200=5,必须12个以上的圆，我估计13个圆也不能不漏缝隙的覆盖，至少需要15个圆吧。
A=1000，B=1000，r=200，最少需要13座信号塔。经过验证了吗？

aimisiyou

happysxyf 发表于 2020-2-27 18:04
此类问题，是否有一般的解决公式，计算出圆的的个数？
s = 4.943+由Kari Nurmela和PatricÖstergå ...

是通过作图得出来的，应该是正确的。作图顺序是先第一、第二层，再做第四层，最后做第三层，最后画那个红色的圆（圆直径比线段还长些）。思路感觉是把零碎的往中间集中，然后一个圆覆盖。

aimisiyou

感觉可以以7个圆覆盖的最大矩形面积为基准，对区域进行划分。剩下的区域按从左到右，从上到下汇集到右下角，先作边上的圆，最后调整四个蓝色的圆位置。所得的圆个数作为一个上界。（不知是不是最少的个数）。

aimisiyou

为了使用最少的圆覆盖全矩形区域，可以理解为每个圆平均覆盖的面积（n个圆覆盖的最大矩形面积除以n）要达到最大，7个圆能覆盖的最大矩形面积为14.08138074，平均一个圆覆盖的面积为2.01162582；为了能提高平均覆盖面积，尽量各拼块中的圆能公用，如图，18个圆，平均一个圆覆盖的面积为2.053920153。
有没有比18个圆更好的组合方式？