3
$\begingroup$

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.

  • 0
    The best known packings for the special case of equal-sized squares in a circle are given at http://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.2010-10-13
  • 0
    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.2010-10-16
  • 0
    @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??2010-10-16
  • 0
    @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?2010-10-16
  • 0
    @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."2010-10-17
  • 0
    @whuber: yes, I do. Thanks for your reply.2010-10-17

1 Answers 1

2

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.