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 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开发者_如何学JAVA 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.

Fully cover a rectangle with minimum amount of fixed radius circles

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? :)

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:

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.

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.

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.

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.

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.