Circle Packing Algorithm

Solution 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.