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
    This question is not clear.2012-03-09
  • 0
    Question is just find the minimum radius of Circle circumscribing four circle of unequal radius. Please see this [link](http://www.palgrave-journals.com/jors/journal/v62/n11/fig_tab/jors2010157f2.html#figure-title) for figure and some solution...But required a short approach/formula...2012-03-09
  • 0
    @jaywendt..Plz help me..2012-03-09
  • 0
    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.2012-03-09
  • 0
    @daniel..Yes ur right..Test case are wrongly posted...2012-03-09
  • 0
    @Avinash: in that case the question is probably clear enough without the examples.2012-03-09
  • 0
    @daniel..Plz give me some solution to solve such problem..except that I posted...2012-03-09
  • 0
    @daniel..I do now..2012-03-09
  • 0
    @daniel..I want some simple approach to do the same..different from Paper..Because paper has solution for n circle and in my case only four. So, if I get some alternate solution based on some single hit formula then it great help for me...2012-03-09
  • 0
    @Avinash: now I think the problem is clear, and the link in your comment connects to a paper which actually does answer your question. It's a nontrivial optimization problem which is set out pretty clearly in the first set of equations in that paper. Perhaps someone with expertise in that area will address your question.2012-03-09
  • 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.