Apollonian Circles

A simple website hosting a demo on apollonian circles, accessible at https://halbfettkaese.github.io/apollonian-circles/.

Click anywhere on the canvas to toggle interactivity.

Mathematical breakdown

The math is based on https://arxiv.org/abs/math/0101066. However, just reading this still does not make it easy to understand how to turn the math written there into useful formulas or how to derive an algorithm from them.

Regular Descartes

The fundamental equations that we will start with are known as Descartes' theorem.

Defining a circle's bend or curvature in relation to its radius $r$ as $b=1/r$¹, Descartes' theorem consists of the following equation between four mutually tangent circles' bends:

$$b_1^2+b_2^2+b_3^2+b_4^2=\frac{1}{2}\left(b_1+b_2+b_3+b_4\right)^2$$

With this being a quadratic equation, it's easy to become inspired to finally find a use for the quadratic formula and solve for the fourth variable. Indeed, exactly this is what the Wikipedia article suggests, as it gives this formula for finding the bend of the 4th circle, while taking the first three circles as given:

$$b_4=b_1+b_2+b_3\pm 2\sqrt{b_1b_2+b_1b_3+b_2b_3}$$

Note how with this, every three mutually tangent circles have two different candidates for a fourth circle that would be tangent to all of the original circles. Furthermore, declaring $D=2\sqrt{b_1b_2+b_1b_3+b_2b_3}$, the above equation simplifies to giving the two solutions:

$$ b_4=b_1+b_2+b_3+D $$ $$ b_4'=b_1+b_2+b_3-D $$

Seeing these equations above each other suggests something that might otherwise not be immediately obvious: When you add $b_4$ and $b_4'$ together, the $D$ and the $-D$ cancel each other out, and you get just a linear equation!

$$ b_4+b_4'=2(b_1+b_2+b_3) $$

This means that all of the pain that comes with applying the quadratic formula wasn't necessary after all. You simply need to start with four mutually tangent circles, declare three of them to be the "original" circles with bends $b_1, b_2, b_3$ while the remaining one is just one of the two circles neighboring them with bend $b_4$, and the equation above gives the easy to compute formula for a unique next circle that is tangent to the first three but distinct from the fourth: $b_4'=2(b_1+b_2+b_3)-b_4$.

Note that the particular choice of which of the four starting circles to pick as the outsider to reflect over the other three circles was mostly arbitrary. You could have picked any one of the four circles to reflect over the others, and each would have given a different new circle that is tangent to the other three of the four original circles.

It is only after starting to iterate this process that you need to be slightly careful about which choice to make: For one of the four circles, replacing it with a "new" circle just undoes the previous move that added the exact circle that the current move would be removing, and would get you back to a state that you previously explored. So an algorithm should always remember which circle is the newest within any group of four, and make sure to only make moves that would replace one of the older three with yet another new circle.

As such, an algorithm for generating more circle bends connecting to the previous ones may look like this:

// Initialize queue of four-circle-groups. Each group has the last added circle as the fourth element.
let queue = [ [-3, 5, 8, 8] ];
let result = [...queue[0]];
function add_group(b1, b2, b3, b4) {
  if (b4 > 80) return; // Skip over the small circles
  result.push(b4);
  queue.push([b1, b2, b3, b4]);
}
for (let i = 0; i < 10 && queue.length > 0; i++) {
  let [b1, b2, b3, b4] = queue.shift();
  add_group(b2, b3, b4, 2*(b2+b3+b4)-b1); // Reflect b1 over b2,b3,b4
  add_group(b1, b3, b4, 2*(b1+b3+b4)-b2); // Reflect b2 over b1,b3,b4
  add_group(b1, b2, b4, 2*(b1+b2+b4)-b3); // Reflect b3 over b1,b2,b4
  // Don't reflect b4 over the others, as that would undo the reflection that just created b4
}

console.log(...result); // -3 5 8 8 45 21 12 77 44 44 53 29 20 77 77 68 56 77 53 32

This recreates the numbers found on this Wikipedia image:

Complex Descartes

As it turned out, all of this is fine and easy, but knowing just the circle bends is useless if we still don't know where the circles should actually be placed. This is where the complex Descartes' theorem comes in. It owes its name to the fact that it is completely analogous to the original Descartes' theorem:

$$ (z_1b_1)^2+(z_2b_2)^2+(z_3b_3)^2+(z_4b_4)^2=\frac{1}{2}\left(z_1b_1+z_2b_2+z_3b_3+z_4b_4\right)^2 $$

In this, $z_1, z_2, z_3, z_4$ are complex numbers that each represent the center of one of the four touching circles. After substituting $u_i:=z_ib_i$, the equation actually becomes the exact same as the original Descartes' theorem, except that the numbers it relates are $u_i$ instead of $b_i$. With this, we can directly apply the same result that we previously derived for the bends to instead be used for computing new circle centers:

$$ u_4'=2(u_1+u_2+u_3)-u_4 $$

This makes it clear that getting the previous algorithm to also work for computing circle centers just means adding more dimensions to the respective linear equations. Once $u$ and $b$ are known for a given circle, the circle center is easy to extract as $z=u/b$.

Starting from three circles

The explanations so far should have made clear how much easier the math is when you start with a group of four mutually tangent circles and use those to generate more such groups of four.

However, this still doesn't answer the question of how you find four of these circles to start with. Finding examples of just three starting circles is easy, for example you could have one big circle of radius $1$ and place two smaller circles of radius $1/2$ along the diameter inside the big circle. But finding a fourth circle by hand is more difficult, and could benefit from a standardized method.

For this, we can again use Descartes' theorem, but this time, we can actually use the results from the quadratic formula on the regular and the complex Descartes' theorem:

$$ b_4=b_1+b_2+b_3\pm 2\sqrt{b_1b_2+b_1b_3+b_2b_3} $$ $$ u_4=u_1+u_2+u_3\pm 2\sqrt{u_1u_2+u_1u_3+u_2u_3} $$

However, this naive approach quickly runs into problems: The first equation has 2 different solutions depending on whether you choose the $+$ or the $-$ sign, and the second equation also has 2 different solutions in the same way. In total, this would give 4 combinations, even though there are always only exactly 2 different circles that are tangent to the original three. One might hope that there is a consistent way in which the sign from one equation can be matched with the sign of the other equation, but after some experimentation, it becomes apparent that every combination has some cases where it is correct and some cases where it is incorrect.

What saves us here is an equation given relatively close to the start of the paper I referenced earlier, Beyond the Descartes circle theorem:

$$ \sum_{j=1}^4 b_ju_j=\frac{1}{2}\left(\sum_{j=1}^4b_j\right)\left(\sum_{j=1}^4u_j\right) $$

The way it arrives at this equation is by first substituting $z_i$ with $z_i + w$ in the original complex descartes' theorem, which is valid because if all circles are shifted by the same amount, they will stay mutually tangent, and comparing the coefficients for different powers of $w$ in the resulting polynomial equation.

This resulting equation is particularly convenient because we now have a linear equation that can be solved for a unique value of $u_4$ given a choice for $b_4$. That means we just get the wanted total of 2 combinations of bend and circle center. Solving the linear equation above for $u_4$, we get:

$$ S:=\frac{1}{2}\sum_{j=1}^4b_j $$ $$ u_4=\frac{-\sum_{j=1}^3 (b_j-S)u_j}{b_4-S} $$

What stands out here is that we're dividing by $b_4-S=b_4-(b_1+b_2+b_3+b_4)/2=-(b_1+b_2+b_3-b_4)/2$, which would lead to problems if this quantity is 0. However, that condition can be restated as $b_4=b_1+b_2+b_3$. When compared to the result of the quadratic formula given above, this can be recognized as being exactly the case where the discriminant was 0 and the quadratic formula gives only one bend. In that case, you can simply use the quadratic formula on the complex Descartes' theorem to get the 2 different circle centers from just the single bend.

With this, we have found a way to always get the 2 different circles that each are tangent to the three original mutually tangent circles.

Summary

Getting the two circles that are tangent to 3 given circles:

1. Start with 3 mutually tangent circles. Their properties can be known through intuition or simple algebra/geometry.
2. Use the quadratic formula to find the two different bends $b4$ and $b4'$ of the two different circles that are tangent to the original 3 circles:
   $$b_4=b_1+b_2+b_3\pm 2\sqrt{b_1b_2+b_1b_3+b_2b_3}$$
   
3. If the two bends are the same (i.e. the discriminant was 0), use the quadratic formula on the complex Descartes' theorem to find the two different circle centers matching that same bend, where $u_i=z_ib_i$, with $z_i$ being the complex number corresponding to the circle center:
   $$u_4=u_1+u_2+u_3\pm2\sqrt{u_1u_2+u_1u_3+u_2u_3}$$
   
4. Otherwise, use the solution to the linear equation to find the unique circle centers matching each of the two found bends:
   $$S=\frac{1}{2}(b_1+b_2+b_3+b_4)$$
   $$u_4=\frac{-\sum_{j=1}^3 (b_j-S)u_j}{b_4-S}$$

Getting the one circle that is tangent to 3 out of 4 given circles:

1. Start with 4 mutually tangent circles with bends $b_1, b_2, b_3, b_4$ and centers $z_1, z_2, z_3, z_4$, with $u_i:=z_ib_i$.
2. A new circle that is tangent to the first three circles is given by $b_4' = 2(b_1+b_2+b_3)-b_4$ and $u_4'=2(u_1+u_2+u_3)-u_4$.

Footnotes

1. You may notice that the circle bends are sometimes negative. This simply determines whether other circles should be on a given circle's inside or outside. In general, two touching circles have one inside the other if the signs of their bends are different. For drawing a circle to the screen, you can always draw the circle using the absolute value of its bend.
   
   Straight lines can also occur as part of these calculations, as they are degenerate forms of a circle in the case where there is 0 bend, or in other words, infinitely large circles. Beyond the Descartes circle theorem describes a method to deal with this using circle inversion, which doesn't even seem computationally complex, but my code worked well enough by just hiding the circles when they became too large, as there were already precision issues before the gigantic circles became straight lines. ↩