5
$\begingroup$

I have question related to circle-packing. The problem is to find the circle of minimum radius enclosing four non-overlapping circles of arbitrary radius. I have to write a program in C for this question but have not been able to find a formula for the radius of the enclosing circle. Any help appreciated.

For more understanding see this link

$\endgroup$
  • $\begingroup$ This question is not clear. $\endgroup$ – Lepidopterist Mar 9 '12 at 16:55
  • $\begingroup$ Question is just find the minimum radius of Circle circumscribing four circle of unequal radius. Please see this link for figure and some solution...But required a short approach/formula... $\endgroup$ – Avinash Singh Mar 9 '12 at 17:03
  • $\begingroup$ @jaywendt..Plz help me.. $\endgroup$ – Avinash Singh Mar 9 '12 at 17:10
  • $\begingroup$ Regarding your "test cases": how can even one circle of radius 2500 be contained in a circle of radius 1837? I looked at the link you posted. To make sense of your question I think the radius of the enclosed circles would have to be smaller. $\endgroup$ – daniel Mar 9 '12 at 18:51
  • $\begingroup$ @daniel..Yes ur right..Test case are wrongly posted... $\endgroup$ – Avinash Singh Mar 9 '12 at 18:54
1
$\begingroup$

Almost exactly a year before this answer was posted (6 August 2015) Mike Bostock encountered this problem while developing his D3.js library, except that the number of circles was arbitrary and they could overlap. He made a solution that works in all these cases, which can be seen (and played around with) here.

The algorithm is a modification of Welzl's algorithm for finding the smallest enclosing circle of a set of points. The modifications that allow it to handle circles are, as explained in the bl.ocks.org link:

  • The test for whether the next point is in the current smallest enclosing circle replaces the point with another circle, and is trivial to implement.
  • The enclosing circle itself is tangent to two or three circles; its radius and position are calculated by any solution to the problem of Apollonius.

Hence the problem posed in the question, the smallest enclosing circle of four non-overlapping circles, can be solved very quickly on a computer.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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