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

  • 0
    Waiting for someone to help.......2012-03-09

1 Answers 1

1

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.