34

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. Hexagonal vs clover

The questions still remain:

  1. Is the regular hexagon pattern itself optimal? Or certain adjustments should be made in parts of the main rectangle.
  2. Are there reasons not to use regular shapes as "ultimate solution"?
  3. Does this question even have an answer? :)
10
  • 1
    This looks more like math than programming. Oct 10, 2011 at 17:35
  • 1
    I would suggest asking that on math.SE math.stackexchange.com
    – yoozer8
    Oct 10, 2011 at 17:35
  • 4
    And if it's not a formula that can solve it, but a complex algorithm? I'll just retag it.
    – Alex
    Oct 10, 2011 at 17:46
  • Is R the same size for every problem? Can the circle "overflow" the area of the rectangle? If the circle can overflow the rectangle and R can change based on the problem, why not just set R = max(X, Y) * 2? Then the circle will cover the entire rectangle and you will only use 1 circle.
    – Dan W
    Oct 10, 2011 at 19:27
  • Given X, Y and R, find N. Yes, circles can overlap, overflow, overaything, as long as it's the minimum number.
    – Alex
    Oct 10, 2011 at 20:44

5 Answers 5

14

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.

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.

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.

In terms of your specific questions:

  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.

  2. 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).

  3. 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.

9

This site attacks the problem from a slightly different angle: Given n unit circles, what is the largest square they can cover?

As you can see, as the number of circles changes, so does the covering pattern.

For your problem, I believe this implies: different rectangle dimensions and circle sizes will dictate different optimal covering patterns.

4
  • ... no wonder I haven't come up with a solution when I was a kid and this was presented to me.
    – Alex
    Oct 10, 2011 at 23:33
  • 1
    Nice! In fact, it is pretty easy to see that the problem discussed at that link is strictly easier than this problem. (Restrict this problem to squares. Observe that the number of circles needed increases monotonically with the size of the square. So, given an algorithm for this problem, you can binary search on the square size to find the largest square -- to arbitrary precision -- coverable by n circles.)
    – Nemo
    Oct 10, 2011 at 23:49
  • @Nemo - That would only work if you knew the largest square coverable by n circles for all n. Unfortunately, I don't think that's the case. For the 12 cases illustrated on the page I linked to, it appears that each case was solved separately.
    – mbeckish
    Oct 11, 2011 at 12:48
  • @mbeckish - I meant if you had an algorithm for solving this problem (given a rectangle, how many circles are needed to cover them?), you could use it as a subroutine to solve the other problem (given n identical circles, what is the largest square they can cover?). Therefore this problem is strictly harder than the other.
    – Nemo
    Oct 11, 2011 at 15:06
2

The hexagon is better than the diamond. Consider the percent area of the unit circle covered by each:

#!/usr/bin/env ruby

include Math

def diamond
  # The distance from the center to a corner is the radius.
  # On a unit circle, that is 1.
  radius = 1

  # The edge of the nested diamond is the hypotenuse of a
  # right triangle whose legs are both radii.
  edge = sqrt(radius ** 2 + radius ** 2)

  # The area of the diamond is the square of the edge
  edge ** 2
end

def hexagon
  # The hexagon is composed of 6 equilateral triangles.
  # Since the inner edges go from the center to a hexagon
  # corner, their length is the radius (1).
  radius = 1

  # The base and height of an equilateral triangle whose
  # edge is 'radius'.
  base = radius
  height = sin(PI / 3) * radius

  # The area of said triangle
  triangle_area = 0.5 * base * height

  # The area of the hexagon is 6 such triangles
  triangle_area * 6
end

def circle
  radius = 1
  PI * radius ** 2
end

puts "diamond == #{sprintf "%2.2f", (100 * diamond / circle)}%"
puts "hexagon == #{sprintf "%2.2f", (100 * hexagon / circle)}%"

And

$ ./geometrons.rb 
diamond == 63.66%
hexagon == 82.70%

Further, regular hexagons are highest-vertex polygon that form a regular tessellation of the plane.

0

According my calculations the right answer is:

D=2*R; X >= 2*D, Y >= 2*D,
N = ceil(X/D) + ceil(Y/D) + 2*ceil(X/D)*ceil(Y/D)

In particular case if the remainder for X/D and Y/D equal to 0, then

N = (X + Y + X*Y/R)/D

Case 1: R = 1, X = 2, Y = 2, then  N = 4

Case 2: R = 1, X = 4, Y = 6, then  N = 17

Case 3: R = 1, X = 5, Y = 7, then  N = 31

Hope it helps.

1
  • Your calculations are only going to be helpful if you can justify them.
    – Teepeemm
    Nov 23, 2015 at 16:37
-2

When the circles are disposed as a clover with four leafs with a fifth circle in the middle, a circle will cover an area equal to R * 2 * R. In this arrangement, the question becomes: how many circles that cover an area of R * 2 * R will cover an area of W * H?, or N * R * 2 * R = W * H. So N = W * H / R * 2 * R.

1
  • Could you draw that? From your description (4 tangent circles with one circle in the middle), the marginal surface for each 3 new added circles equals 4 * R^2 (which means that the marginal surface of one circle equals 4/3 * R^2. Whereas when using squares from single circles gives a marginal surface of 2 * R^2. Either the clover is a less optimal solution, or I didn't get your idea.
    – Alex
    Oct 10, 2011 at 18:26

Your Answer

Reminder: Answers generated by Artificial Intelligence tools are not allowed on Stack Overflow. Learn more

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.