完全覆盖具有最小固定半径圆的矩形
我有这个问题已经有几年了.一段时间以前,我的城镇正在进行信息学竞赛.我没有解决它,我的老师没有解决它.我没有见过任何能够解决它的人.我不认识任何人知道给出答案的正确方法,所以我决定在这里发布:
泽问题
给定一个矩形,X乘Y,找到具有固定给定半径R的最小圆N数,这是完全覆盖矩形的每个部分所必需的.
我想办法解决它,但我没有什么明确的.如果每个圆圈定义一个内部矩形,那么R^2 = Wi^2 + Hi^2,每个圆圈覆盖的实际区域的宽度和高度在哪里Wi和哪个.起初我以为我应该等于任何= ,同样的.这样,我可以通过使宽度/高度比率与主矩形(= )相等来简化问题.那样,.但是这种解决方案肯定是错误的,如果大大超过,反之亦然.
第二个想法是= 对于任何给定的.这样,正方形可以最有效地填充空间.但是,如果仍然存在非常窄的条带,则使用矩形填充它会更好,或者更好 - 在此之前使用矩形作为最后一行.
然后我意识到没有一个想法是最优的,因为我总能找到更好的方法来做到这一点.它将永远接近最终,但不是最终的.HiiWiWjijHWi/HiX/YN=X/WiXYWiHii
编辑
在某些情况下(大矩形)连接六边形似乎比连接正方形更好.
进一步编辑
这里是两种方法的比较:三叶草与六角形.对于大型表面,六角形显然更好.但我确实认为,当矩形足够小时,矩形方法可能更有效.这是一种预感.现在,在图片中,您会在左侧看到14个圆圈,在右侧看到13个圆圈.虽然表面的差异比一个圆圈大得多(双倍).这是因为它们在左侧重叠较少,因此浪费的表面较少.
问题仍然存在:
- 正六边形图案本身是否最佳？或者应该在主矩形的某些部分进行某些调整.
- 有没有理由不使用常规形状作为"终极解决方案"？
- 这个问题甚至有答案吗？:)
对于与R相比较大的X和Y,六边形(蜂窝状)图案接近最佳.X方向上的圆心之间的距离是sqrt(3)*R.Y方向上的行之间的距离是3*R/2,因此您需要大致X*Y/R^2 * 2*/(3*sqrt(3))圆形.
如果使用方形图案,水平距离会更大(2*R),但垂直距离要小得多(R),因此您需要大约X*Y/R^2 * 1/2圆圈.因为2/(3*sqrt(3) < 1/2,六边形图案是更好的交易.
请注意,这只是一个近似值.通常可以稍微摇动常规图案以使某些东西适合标准图案不适合的位置.如果X和Y与R相比较小则尤其如此.
就您的具体问题而言:
六边形图案是整个平面的最佳覆盖.在X和Y有限的情况下,我认为通常可以获得更好的结果.简单的例子是当高度小于半径时.在这种情况下,您可以将一行中的圆圈进一步移开,直到每对圆的交叉点之间的距离等于Y.
具有规则模式会对解决方案施加额外限制,因此在这些限制下的最佳解决方案可能不是最佳解决方案.一般来说,有些不规则的模式可能更好(参见由mbeckish链接的页面).
同一页面上的示例都是特定的解决方案.具有更多圆圈的解决方案稍微类似于六边形图案.但是,似乎没有封闭形式的解决方案.
npc*_*diu -2
当这些圆被布置为有四片叶子的三叶草，第五个圆在中间时，一个圆将覆盖等于 的面积R * 2 * R。在这种排列中，问题就变成了：有多少个面积为 的圆R * 2 * R将覆盖面积为 的面积W * H？， 或者N * R * 2 * R = W * H。所以N = W * H / R * 2 * R。