Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Rectangles will all be the same size, circle may vary.

I was discussing this with a friend and he said to just start placing them in the middle and moving outwards but it seems that you could free up more space for rectangles around the edges if you moved that center of mass to one side and maybe put some space between the rectangles.

Let me know if any of this is confusing or if you have heard of a good method for doing this.

share|improve this question
    
The best known packings for the special case of equal-sized squares in a circle are given at www2.stetson.edu/~efriedma/squincir . Note that only the first two have been proved optimal, so I expect there is no known algorithm for finding such optimal packings in the general case. –  Rahul Oct 13 '10 at 20:14
    
It seems to me that due to symmetrical reasons the centre of one of the rectangles and the centre of the circle has to be the same point. –  Américo Tavares Oct 16 '10 at 20:11
    
@Américo: I can put four rectangles of dimensions w and h into a unit circle where w^2 = 32/35 and h^2 = 12/35. Can you find a way where one of these rectangles is concentric with the circle?? –  whuber Oct 16 '10 at 21:52
    
@whuber: I was quite wrong. Your configuration covers $\frac{32\sqrt{6}}{35\pi }\approx 72\%$ of the unit circle, while 4 squares with side $\frac{\sqrt{2}}{2}$ only cover $\frac{2}{\pi }\approx 64\%$. Just a curiosity: Has your configuration point symmetry? –  Américo Tavares Oct 16 '10 at 22:34
    
@Américo: If by "point symmetry" you mean symmetric with respect to the reflection about the circle's center, the answer in this case is yes, but the answer in general is no. For instance, I cannot find any such solution where the rectangle dimensions are 1 - e and 2, with e very small and positive, and the circle has radius sqrt(5 - 2e). Even if I have erred--I haven't exhaustively checked this example--the point is that there seems to be no argument that optimal solutions must have some "symmetry." –  whuber Oct 17 '10 at 14:58
show 1 more comment

1 Answer

up vote 2 down vote accepted

As Rahul's comment indicates, there is no algorithm known to achieve an optimal packing. However, some effective heuristics have been developed. For example, there is a 2010 paper by Andrea Cassioli and Marco Locatelli entitled "A heuristic approach for packing rectangles in convex regions" (PDF download). Here is their abstract:

In this paper we propose a heuristic approach for the problem of packing equal rectangles within a convex region. The approach is based on an Iterated Local Search scheme (or, using a terminology employed for continuous problems, a Monotonic Basin Hopping), in which the key step is the perturbation move. Different perturbation moves, both combinatorial and continuous ones, are pro- posed and compared through extensive computational experiments on a set of test instances. The overall results are quite encouraging.

This recent paper has 38 references, so this should give you much to pursue and ponder.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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