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