# Space filling with circles of unequal radii

Here is my problem:

• I have a bunch of circles that I need to display inside a canvas.
• There are an arbitrary number of circles, each with a predefined radius.
• The summed area of circles is always smaller than the area of the canvas.

I want to position the circles so that they take up the maximal space available inside the canvas, without touching each other.

Here is an example of what I am trying to achieve:

I am unsure about how to model the algorithm to solve this problem. Specifically, I don't understand which function(s) I need to maximize to find the maximum of the "global" inter-circle distance function. I am not even sure if that's the right criterion to maximize to achieve a "balanced" result.

My first "brute force" idea was the following:

1. For each circle:
• Calculate the shortest distances between its border and each other circle's border.
• Sum all of these distances (call that X).
2. Calculate the sum of all circles' X.
3. Randomly change the distances between the circles, with the constraint that they can't touch each other.
4. Redo 1-3 for a preset number of iterations and take the maximal value obtained at step (2).

However, this does not seem "elegant" from a mathematical perspective; I'm sure there is a better way to do it. Also, ideally, the results would be deterministic (i.e. same input always produce same output), which can't be accomplished with this method. Could anyone point me in the right direction?

-
This question was answered on SO: stackoverflow.com/questions/9730989/… –  louism Nov 27 '13 at 1:30

Place the largest circle somewhere, perhaps $\frac{1}3$ of the way along from the bottom left corner. Circumscribe a square around it. Find the rectangle of greatest area that will fit in the remaining space and place the next largest circle with its centre in the centre of this rectangle. Circumscribe a square around it, then do the same for the $3^{rd}$ largest circle and continue until all the circles have been placed.