找回密码
 欢迎注册
查看: 42775|回复: 20

[原创] 最大覆盖问题

[复制链接]
发表于 2020-2-25 23:57:46 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
在一块矩形区域(长为A、宽为B)布置信号塔,已知信号塔信号覆盖半径为r,求至少需要设置几座信号塔才能覆盖全区域?信号塔如何布置?
如图给出的是A=1000,B=1000,r=200,最少需要13座信号塔。
有没有相关算法?
567.png
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-2-26 21:27:31 | 显示全部楼层
圆的相交弦构成正多边形最合理,而平面正多边形镶嵌只有正三角形、正方形和正六边形三种。所以先把要覆盖的矩形区域进行多边形镶嵌划分,然后用圆覆盖。找出圆最少的那种就行。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-2-27 00:01:07 | 显示全部楼层
之前也想过把圆看成圆内接正方形,但得出的正方形个数比实际需要的圆个数要大。用正多边形(如正八边形),边上和中间分布的小缝隙又太分散。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-2-27 10:02:27 | 显示全部楼层
如果A=2.5r,B=1.5r,最少需要几个圆才能覆盖全区域?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-2-27 16:44:24 来自手机 | 显示全部楼层
https://www2.stetson.edu/~efriedma/circovsqu/
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-2-27 17:39:30 | 显示全部楼层

谢谢提供参考!我自己琢磨的7个圆的情况与参考图相似,但参考图覆盖的是正方形,其实覆盖的最大矩形(非正方形)面积为14.08138074。其左上角夹角为sin(2a)+sin(a)取最大值时的弧度值。
-496dc4de9ca57e17.png
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-2-27 18:04:59 | 显示全部楼层
此类问题,是否有一般的解决公式,计算出圆的的个数?
s = 4.943+由Kari Nurmela和PatricÖstergård在2000年发现。边径比1000/200=5,必须12个以上的圆,我估计13个圆也不能不漏缝隙的覆盖,至少需要15个圆吧。
A=1000,B=1000,r=200,最少需要13座信号塔。经过验证了吗?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-2-27 18:36:49 | 显示全部楼层
happysxyf 发表于 2020-2-27 18:04
此类问题,是否有一般的解决公式,计算出圆的的个数?
s = 4.943+由Kari Nurmela和PatricÖstergå ...

是通过作图得出来的,应该是正确的。作图顺序是先第一、第二层,再做第四层,最后做第三层,最后画那个红色的圆(圆直径比线段还长些)。思路感觉是把零碎的往中间集中,然后一个圆覆盖。 123.png
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-2-27 20:23:43 | 显示全部楼层
感觉可以以7个圆覆盖的最大矩形面积为基准,对区域进行划分。剩下的区域按从左到右,从上到下汇集到右下角,先作边上的圆,最后调整四个蓝色的圆位置。所得的圆个数作为一个上界。(不知是不是最少的个数)。
654.png
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-2-27 22:39:22 | 显示全部楼层
为了使用最少的圆覆盖全矩形区域,可以理解为每个圆平均覆盖的面积(n个圆覆盖的最大矩形面积除以n)要达到最大,7个圆能覆盖的最大矩形面积为14.08138074,平均一个圆覆盖的面积为2.01162582;为了能提高平均覆盖面积,尽量各拼块中的圆能公用,如图,18个圆,平均一个圆覆盖的面积为2.053920153。
有没有比18个圆更好的组合方式?
999.png
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-29 20:10 , Processed in 0.074623 second(s), 19 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表