Given a rectangle of area $n\times m$ and identical circles with radius $r$. What is the optimal solution for covering this rectangle with minimum number of circles?
I found a relative solution here.
Should I have to first partition this rectangle with a group of smaller rectangles, and then use circumscribed circles to cover these smaller rectangles?
Is there any optimal solutions?
Best Answer
This question is in part based on answers to this question on Stack Overflow.
No optimal solution
There is no known way to find optimal solutions.
Erich's Packing Center (by Erich Friedman) has a page on circles covering squares. This is related to your problem, and in fact your problem is at least as hard as that problem. Obviously, asking about squares only can be no harder than asking about all rectangles. Furthermore, assume you had an algorithm to find an optimal solution according to your question. Then you could use that algorithm in a binary search, increasing the size of the square (i.e. rectangle) by a bit and using the circle count from your algorithm to see if the number of circles is still sufficient. By this approach, you could approximate the maximal possible square size for a given circle count to arbitrary precision.
So even though your problem is at least as hard as the problem of finding the maximal size of a square that can be covered by a given number of unit circles, there appears to be no general solution to the latter. For some small counts, an solution has been proven to be optimal, denoted by the phrase “proven by …” on the page I referenced. Other configurations are termed “found by …”, indicating that they are the best configuration known to the author, but that he is not aware of any proof of optimality.
Therefore, you should not expect a really optimal solution in the strict sense, although of course a breakthrough discovery always is a possibility.
Good solution
If you weaken your requirement of optimality, you are asking about “good” ways to cover your rectangle. As your comment indicates that your circles are much smaller than the rectangle, you may for the moment ignore the boundary, and instead examine infinite covers. It turns out that the infinite circle cover with least density is the hexagonal one. (I haven't found an article to that effect just now, so if you need a reliable source for this, feel free to post a reference-request.) So by cutting out a rectangular portion of such a hexagonal cover, you'll get the lowest possible density over the majority of your area, and perhaps slightly suboptimal solutions near the boundary.
As the hexagonal lattice will lead to smaller density than the square lattice, you should partition your rectangle not into rectangles but instead into regular triangles, inscribed into your disk of radius $r$. You may get partial triangles near the rim. Unless those parts are already completely covered by some other circle, you'll still need full circles for those partial triangles, which corresponds to the lack of optimality.