用最少的固定半径圆完全覆盖一个矩形 [英] Fully cover a rectangle with minimum amount of fixed radius circles

问题描述

我遇到这个问题已有几年了.前一段时间在我镇举行的一次信息学比赛中.我没有解决，我的老师也没有解决.我还没有遇到任何能够解决这个问题的人.我认识的人都不知道给出答案的正确方法，因此我决定在此处发布答案:

I've had this problem for a few years. It was on an informatics contest in my town a while back. I failed to solve it, and my teacher failed to solve it. I haven't met anyone who was able to solve it. Nobody I know knows the right way to give the answer, so I decided to post it here:

Ze问题

给定一个矩形，X乘以Y，求出具有固定给定半径R的最小圆N，这是完全覆盖矩形的每个部分所必需的.

Given a rectangle, X by Y, find the minimum amount of circles N with a fixed given radius R, necessary to fully cover every part of the rectangle.

我曾想过解决问题的方法，但我没有明确的定义.如果每个圆都定义一个内部矩形，则R^2 = Wi^2 + Hi^2，其中Wi和Hi是每个圆i覆盖的实际区域的宽度和高度.起初，我认为对于任何i = j，我都应使Wi等于Wj，对于H相同.这样，我可以通过使宽高比等于主矩形(Wi/Hi = X/Y)来简化问题.这样，N=X/Wi.但是，如果X大大超过Y或相反，该解决方案肯定是错误的.
第二个想法是对于任何给定的i，Wi = Hi.这样，正方形可以最有效地填充空间.但是，如果仍然存在非常狭窄的条带，则最好使用矩形填充它，或者更好-在此之前的最后一行也使用矩形.
然后我意识到，没有一个想法是最优的，因为我总能找到更好的方法.它将始终接近最终，但不是最终.

I have thought of ways to solve it, but I have nothing definite. If each circle defines an inner rectangle, then R^2 = Wi^2 + Hi^2, where Wi and Hi are the width and height of the practical area covered by each circle i. At first I thought I should make Wi equal to Wj for any i=j, the same for H. That way, I could simplify the problem by making the width/height ratios equal with the main rectangle (Wi/Hi = X/Y). That way, N=X/Wi. But that solution is surely wrong in case X greatly exceeds Y or vice versa.
The second idea was that Wi=Hi for any given i. That way, squares fill space most efficiently. However if a very narrow strip remains, it's much more optimal to use rectangles to fill it, or better yet - use rectangles for the last row before that too.
Then I realized that none of the ideas are the optimal, since I can always find better ways of doing it. It will always be close to final, but not final.

修改
在某些情况下(大矩形)，连接六边形似乎比连接正方形更好.

Edit
In some cases (large rectangle) joining hexagons seem to be a better solution than joining squares.

进一步编辑
这是两种方法的比较:三叶草与六角形.六角形显然适用于较大的表面.但是，我确实认为，如果矩形足够小，则矩形方法可能会更有效.这是预感.现在，在图片中，您会看到左侧的14个圆圈，右侧的13个圆圈.虽然表面相差一个圆大得多(两倍).这是因为它们在左侧的重叠较少，从而减少了表面浪费.

Further Edit
Here's a comparison of 2 methods: clover vs hexagonal. Hexagonal is, obviously, better, for large surfaces. I do think however that when the rectangle is small enough, rectangular method may be more efficient. It's a hunch. Now, in the picture you see 14 circles on the left, and 13 circles on the right. Though the surface differs much greater (double) than one circle. It's because on the left they overlap less, thus waste less surface.

问题仍然存在:

1. 正六边形图案本身是否最优?或应在主​​矩形的某些部分中进行某些调整.
2. 有没有理由不使用规则形状作为最终解决方案"?
3. 这个问题甚至有答案吗? :)

推荐答案

对于与R相比较大的X和Y，六角形(蜂窝)图案接近最佳. X方向上的圆心之间的距离为sqrt(3)*R. Y方向上行之间的距离为3*R/2，因此您大约需要X*Y/R^2 * 2*/(3*sqrt(3))个圆.

For X and Y large compared to R, a hexagonal (honeycomb) pattern is near optimal. The distance between the centers of the circles in the X-direction is sqrt(3)*R. The distance between rows in the Y-direction is 3*R/2, so you need roughly X*Y/R^2 * 2*/(3*sqrt(3)) circles.

如果使用正方形图案，则水平距离较大(2*R)，而垂直距离较小(R)，因此大约需要X*Y/R^2 * 1/2个圆.从2/(3*sqrt(3) < 1/2开始，六角形图案更好.

If you use a square pattern, the horizontal distance is larger (2*R), but the vertical distance is much smaller (R), so you'd need about X*Y/R^2 * 1/2 circles. Since 2/(3*sqrt(3) < 1/2, the hexagonal pattern is the better deal.

请注意，这只是一个近似值.通常可以稍微调整常规模式，以使某些内容适合标准模式不适合的地方.如果X和Y比R小，则更是如此.

Note that this is only an approximation. It is usually possible to jiggle the regular pattern a bit to make something fit where the standard pattern wouldn't. This is especially true if X and Y are small compared to R.

关于您的具体问题:

1. 六角形图案是整个平面的最佳覆盖.使用X和Y有限，我认为通常有可能获得更好的结果.一个简单的例子是当高度小于半径时.在这种情况下，您可以将一行中的圆进一步分开，直到每对圆的相交点之间的距离等于Y.

1. The hexagonal pattern is an optimal covering of the entire plane. With X and Y finite, I would think it is often possible to get a better result. The trivial example is when the height is less than the radius. In that case you can move the circles in the one row further apart until the distance between the intersecting points of every pair of circles equals Y.

具有规则模式会对该解决方案施加其他限制，因此，除去这些限制后，在这些限制下的最佳解决方案可能不是最佳的.通常，有些不规则的模式可能会更好(请参见通过乱码链接的页面).

Having a regular pattern imposes additional restrictions on the solution, and so the optimal solution under those restrictions may not be optimal with those restrictions removed. In general, somewhat irregular patterns may be better (see the page linked to by mbeckish).

同一页面上的示例都是特定的解决方案.具有更多圆圈的解决方案在某种程度上类似于六边形图案.不过，似乎没有封闭形式的解决方案.

The examples on that same page are all specific solutions. The solutions with more circles resemble the hexagonal pattern somewhat. Still, there does not appear to be a closed-form solution.

这篇关于用最少的固定半径圆完全覆盖一个矩形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！