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.

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:

Circles

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?

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

1 Answer 1

Quicker than the brute force idea, but only an approximation:

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.

share|improve this answer
    
Interesting. I'll give it a try and post an update. –  louism Mar 15 '12 at 17:54

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.