geometry - Covering an arbitrary area with circles of equal radius

Question

How would an algorithm work that covers an arbitrary area with circles of equal radius?

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.

Is there an algorithm that will handle this?

Answer 1

I know that question may be a bit outdated but recently I got a similar problem with covering geographic area with equal circles using hexagonal grid and this is how I solved it:

1. my input data were radius of circle given in meters and coordinates of borders of the area
2. first I found the bounds rectangle that covers given area
3. then starting from the left bottom I move the point by distance equaling double the height of the triangle used to build the hexagon (its side is the same of radius of my circle) and bearing of 0 degrees using Vincenty's formulae
4. for each point I found, I check if it intersects with my input area, if does I save it, other way I skip it
5. when I got to the edge I do one more check to ensure that I will get all points within the are
6. I move the point by bearing of 60 degrees, check it, then by 120 degrees, check again
7. go back to 3rd step but now I move the points by bearing of 180 degrees
8. and the edge again one more check and then like in step 6th but first 120 degrees then 60 degrees
9. continue until you got to the top edge of rectangle

like in given image, of course you can increase the accuracy by decreasing radius of circle

I know that this is not the best option but it works pretty well for me.

I hope it's quite understandable and will help anyone.