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 problem
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.
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.
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.
The questions still remain:
- Is the regular hexagon pattern itself optimal? Or certain adjustments should be made in parts of the main rectangle.
- Are there reasons not to use regular shapes as "ultimate solution"?
- Does this question even have an answer? :)