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?

  • $\begingroup$ See www2.stetson.edu/~efriedma/circovsqu for the special case where the rectangle is a circle, and for the slightly different case where the number of circles is prescribed, not their radius. $\endgroup$ – MvG Oct 18 '12 at 8:54
  • $\begingroup$ Thanks for you answer. I have seen this article before. It uses only a few circles to cover the rectangle $B$. But if the circle is much smaller than the rectangle $B$, how should I solve the problem? $\endgroup$ – Kate YAN Oct 19 '12 at 14:45
  • $\begingroup$ If the circle is very much smaller than the rectangle, then you'd probable best use the hexagonal circle cover, which is the infinite cover with least density, and cut a sufficient portion from that. In general thsi won't be optimal in the finite case, but the greater the difference between circle and rectangle size, the less the relative error will become. By the way, I just noticed that this question on Stack Exchange asks pretty much the same thing you do. With similar answers, though none got accepted yet. $\endgroup$ – MvG Oct 19 '12 at 15:15

This question is in part based on answers to this question on Stack Overflow.

No optimal solution

Is there any optimal solutions?

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

Should I have to first partition this rectangle with a group of smaller rectangles, and then use circumcircles to cover these smaller rectangles?

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.

  • $\begingroup$ Thank you for your detailed answer. I agree with the solution of partitioning the rectangle into hexagonal lattice. But I don't think that hexagonal lattice is always better than rectangles. It depends on the proportion of n, m and r. $\endgroup$ – Kate YAN Oct 22 '12 at 9:01
  • $\begingroup$ @KateYAN, don't claim that the hexagonal lattice will always be better. I'm just saying that it's better in the infinite case, and that according to your comment, $r ≪ m,n$ so it should be better for you. $\endgroup$ – MvG Oct 22 '12 at 14:39
  • $\begingroup$ Yes, you are right. Thanks. $\endgroup$ – Kate YAN Oct 23 '12 at 23:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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