Covering an arbitrary area with circles of equal radius

Question

How would an algorithm work that achieves this goal? EDIT: For clarification: The radius of the circle and the size and shape of the area are arbitrarily given. The area should be covered with as few circles as possible. The circles may overlap.

Answer 1

Um, how about one gigantic circle? I think you need to specify this problem a bit more.

Answer 2

Without knowing more about your constraints, I would suggest taking a regular covering of the plane, with disks corresponding to the regular hexagons of an hexagonal tiling. Then keep all disks intersecting the shape.

Answer 3

Hope I have understood your question right...

It can be proved that Hexagonal Close Packing (HCP) of spheres covers the maximum volume, using spheres. Therefore, I assume that doing HCP with circles will also cover the maximum area using circles. Tessellate your area with triangles and place a circle with the centre at each vertex of the triangle, with the radius half the length of the side of the triangle. See this for an image of the algorithm I am talking about.

Note: This is similar to the close packing of atoms in a unit cell.

EDIT: My previous method covers as much of the area as possible, without overlapping. If overlapping is allowed, then (I believe that) the following method would cover the whole area with minimum overlapping.

As you probably know, there are only 3 tessellations of 2D space with regular polygons - using squares, triangles or hexagons. The strategy is to tessellate using one of these polygons and then circumscribe a circle to every polygon. A hexagon would waste the minimum area using this method.

Therefore, from the radius of the given circle, calculate the size of the needed hexagons, tessellate the area using the hexagons and then circumscribe a circle onto each hexagon.

NB: Eric Bainville suggested a similar method.

-- Flaviu Cipcigan

Answer 4

Exactly, as Hans I have a general a problem what kind of "covering" do you need? For example, one can say that a 2d HCP method recalled by Flaviu does NOT covers the area, because there are a free spaces between circles.

Answer 5

Not enough constraints.

Are the circles allowed to extend beyond the shape to be covered? If they are then one big circle will do the trick. If they're not and the shape has straight lines the circles will have to be infinitesimally small. If they're not and the shape is made of curves then the smallest radius will define the size of the largest circle that can be used.