# Theory

* wikipedia
* mathforum : Problem of Apollonius

# How to compute and draw Apollonian gasket ?
## Notation

* Apollonian gasket = curvilinear Sierpinski gasket = Leibniz packing = Apollonian packing
* stage = level = step
* incircle = inscribed circle = circle inside 3 circles = inner circle
* gap = curvilinear triangle = ideal triangle ( because the sides are tangent at each vertix and the angle between them is zero) = region between 3 tangent circles

## Algorithms

Apollonian gasket can be made using these algorithms:
* Mandelbrot algorithm( using circle inversion)
* Soddy's algorithm ( using circle Descartes theorem )
* IFS algorithm by Alexei Kravchenko and Dmitriy Mekhontsev
All algorithms give state after n stages. It is an approximation of limit set which is made of infinite number of stages (cicles).

### Mandelbrot algorithm

(to do )

### Soddy's algorithm

It will be explained by example gasket with initial configuration : 3 inner circles with integer curvatures
    $(k_{ia},k_{ib},k_{ic})=(32,32,33)$
This algorithm uses:
* previous circles defined by centers $c_{n}$ and curvatures $k_{n}$
* circle Descartes theorem to compute curvature of next circle $k_{4}$
    $k_{4}=k_{1}+k_{2}+k_{3}\pm 2{\sqrt {k_{1}k_{2}+k_{2}k_{3}+k_{3}k_{1}}}$
* complex circle Descartes theorem to compute center of next circle $c_{4}$
    $c_{4}={\frac {c_{1}k_{1}+c_{2}k_{2}+c_{3}k_{3}\pm 2{\sqrt {k_{1}k_{2}c_{1}c_{2}+k_{2}k_{3}c_{2}c_{3}+k_{1}k_{3}c_{1}c_{3}}}}{k_{4}}}$
When center of outer circle is at origin one has to chose solutions in case of centers. It is easier when the all gasket is in the first quadrant of Cartesian plane. Then all centers have positive parts ( real and imaginary ).

#### Functions
##### Functions for computing curvature and center

    $f_{p}(a_{1},a_{2},a_{3}){\overset {\underset {\mathrm {def} }}{=}}a_{1}+a_{2}+a_{3}+2\cdot {\sqrt {a_{1}a_{2}+a_{2}a_{3}+a_{3}a_{1}}}$
    $f_{\color {Red}m}(a_{1},a_{2},a_{3}){\overset {\underset {\mathrm {def} }}{=}}a_{1}+a_{2}+a_{3}{\color {Red}-}2\cdot {\sqrt {a_{1}a_{2}+a_{2}a_{3}+a_{3}a_{1}}}$
Note that variable $a_{i}$ can be curvature $k_{i}$ or $c_{i}*k_{i}$ so $f_{p}$ can be used for computing both curvatures and centers

##### Functions for computing ck list

It is easier to use a list $ck$ which defines circle. It consist of two element center $c$ and curvature $k$ :
$ck=[c,k]$
$c=ck[1]$
$k=ck[2]$
Now one can define new functions ( Maxima CAS code) for computing 4-th circle mutually tangent to 3 given circles:
Function $f_{pp}$ uses $f_{p}$ function for computing both center and curvature. It is used for computing almost all circles without outer circle and hard circles
Function $f_{pm}$ uses $f_{p}$ function for computing curvature and $f_{m}$ function for computing center. It is used for computing hard circles.
Function $f_{mm}$ uses $f_{m}$ function for computing both center and curvature. It is used for computing outer circle.

##### Functions for filling gaps
#### Construction

* initial stage : 3 mutually tangent circles = $(k_{ia},k_{ib},k_{ic})$
* zero stage : 2 circles tangent to previous : outer circle $ck_{0out}$ and inner circle $ck_{0in}$, where :
    ${\color {Red}ck}_{0out}=f_{\color {Red}mm}(ck_{ia},ck_{ib},ck_{ic})$
    $ck_{0in}=f_{pp}(ck_{ia},ck_{ib},ck_{ic})$
* first stage : there are 6 gaps ( = curvilinear triangles) between previous circles. Three gaps are peripheral ( near outer circle) and three are medial ( near inner circle). Put one circle in each gap :
    $ck_{1a}=f_{pp}(ck_{ia},ck_{ib},ck_{0out})$
    $ck_{1b}=f_{pp}(ck_{ib},ck_{ic},ck_{0out})$
    ${\color {Red}c}k_{1c}=f_{p{\color {Red}m}}(ck_{ic},ck_{ia},ck_{0out})$
    $ck_{1d}=f_{pp}(ck_{ia},ck_{ib},ck_{0in})$
    $ck_{1e}=f_{pp}(ck_{ib},ck_{ic},ck_{0in})$
    $ck_{1f}=f_{pp}(ck_{ic},ck_{ia},ck_{0in})$
Each new circle placed in the gap makes three new gaps (trifurcation).
* second stage : there are 18 (6*3) new gaps. Put one circle in each gap using $f_{pp}$ function except one hard circle :
    ${\color {Red}c}k_{2cc}:f_{p{\color {Red}m}}(ck_{ic},ck_{1c},ck_{0out})$
* next stages : Put one circle in each gap at each stage. At each stage there is only one hard circle and it is in $1c$ gap.

#### Algorithm for programmers

Because all circles are inscribed in outer circle so it is easier to start from it.
* choose size of quadratic image $side$
* compute radius of outer circle :
    $r_{0out}={\frac {side}{2}}$
* place outer circle in first quadrant of Cartesian plane :
    $c_{0out}=r_{0out}+r_{0out}*i$
* compute radius of 3 equal initial circles
    $a=1+{\frac {2}{\sqrt {3}}}$
    $r_{i}={\frac {r_{0out}}{a}}$
* find centers of initial circles. For example place one circle $ia$ in upper row and 2 circles ($ib$ and $ic$) in lower row.
Then centers of these circles are vertices of equilateral triangle, with side of the triangle $=2*r_{i}$ so :
$height=r_{i}*{\sqrt {3}}$
$c_{ia}=r_{0out}+(2*r_{0}out-r_{i})*i$
$c_{ib}=(r_{0out}+r_{i})+(2*r_{0}out-r_{i}-height)*i$
$c_{ic}=(r_{0out}-r_{i})+(2*r_{0}out-r_{i}-height)*i$
* compute inner circle $0in$
    $ck_{0in}=f_{pp}(ck_{ia},ck_{ib},ck_{ic})$
* "Now we have a configuration to start" There is 6 gaps to fill. 5 gaps are easy and one gap $1c$ is hard to fill.

#### Relation between circles

    ${\color {Red}ck}_{0out}=f_{\color {Red}mm}(ck_{ia},ck_{ib},ck_{ic})$
    $ck_{0in}=f_{pp}(ck_{ia},ck_{ib},ck_{ic})$
    ${\color {Red}ck}_{ia}=f_{\color {Red}mm}(ck_{ib},ck_{ib},ck_{0out})$
    $c{\color {Red}k}_{ib}=f_{{\color {Red}m}p}(ck_{ia},ck_{ic},ck_{0out})$
    ${\color {Red}ck}_{ic}=f_{\color {Red}mm}(ck_{ia},ck_{ib},ck_{0out})$

#### Number of circles

* number of new circles at stage n = $2*3^{n}$
* total number of circles after n stages = $2+3^{n+1}$
where $n>=0$
For example :
* stage -1 = initial configuration ( 3 inner circles )
* stage 0 gives 2 new circles ( one outer and one most inner ). All circles = 5
* stage 1 gives 6 new circles ( all circles = 11 )
* stage 2 gives 18 new circles ( all circles = 29 )
* stage 3 gives 54 new circles ( all circles = 83)
* stage 4 gives 162 new circles ( all circles = 245)
* stage 5 gives 486 new circles ( all circles = 731)
* stage 6 gives 1 458 new circles ( all circles = 2 189 )
* stage 7 gives 4 374 new circles ( all circles = 6 563 )
* stage 8 gives 13 122 new circles ( all circles = 19 685 )
* stage 9 gives 39 366 new circles ( all circles = 59 051 )
* stage 10 gives 118 098 new circles ( all circles = 177 149 )
* stage 11 gives 354 294 new circles ( all circles = 531 443 )
* stage 12 gives 1 062 882 new circles ( all circles = 1 594 325 )
* stage 13 gives 3 188 646 new circles ( all circles = 4 782 971 )
* stage 14 gives 9 565 938 new circles ( all circles = 14 348 909 )
* stage 15 gives 28 697 814 new circles ( all circles = 43 046 723 )
* stage 16 gives 86 093 442 new circles ( all circles = 129 140 165 )
* stage 17 gives 258 280 326 new circles ( all circles = 387 420 491 )
* stage 18 gives 774 840 978 new circles ( all circles = 1 162 261 469 )
* stage 19 gives 2 324 522 934 new circles ( all circles = 3 486 784 403 )
* stage 20 gives 6 973 568 802 new circles ( all circles = 10 460 353 205 )
It can be computed using this Maxima CAS code :
Number of circles grows rapidly and makes problems caused by big file size. One can :
* use only stages up to 5-7. It seems to be sufficient to give good image in a short time.
* do not draw circles which are small ( have a small radius < pixel size)
* convert svg file to png ( for example using Image Magic : "convert a.svg a.png" ). Then for stage 12 svg image has 128 MB and png file only 57 KB.
* be happy that you have so detailed picture and wait a long time to load file or see how system hangs up (:-))

#### Curvatures

Note that only one curvature has been computed with $f_{\color {Red}m}$ function.
It is $k_{0out}$. It is also only one negative curvature.
All the rest have been comuted with $f_{p}$ function.
| stage $n\,$ | curvatures |
| -1 | $(32,32,33)\,$ |
| 0 | $({\color {Red}-15},209)\,$ |
| 1 | $(68,65,68,516,513,516)\,$ |
| 2 | $(953,1481,1484,945,1476,1476,953,1484,1481,281,137,140,273,132,132,68,137,140)\,$ |

#### Example programs
##### Haskell and EDSL Diagrams

* Image and code by Brent Yorgey
* diagrams code

##### Java

CirclePack program by Ken Stephenson

##### Maxima CAS

Program is explained above, and src is in description of Apollonian_rc_6.svg

##### Common Lisp

To run put apollonian.lisp file in your home directory and in Emacs/slime. To get another step change *max-step*
Load file to run code ( batch mode ) :

##### JavaScript

This is an incremental algorithm that maintains a queue of triples of touching circles. The main loop starts at the front of the queue, removing a triple and filling it with the required circle, adding the resulting circle to a list of circles to draw as SVG and adding the three triples that result from adding the circle to the back of the computation queue. As a bonus feature, the circles are coloured so that no two neighbours have the same colour.
Usage: concatenate the two SVG boilerplate parts and the middle Javascript part into one SVG file and load into a web browser (or another SVG viewer that supports Javascript or ECMAScript).

# See also

* mathcurve : Apollonian gasket and apollonian packing
* http://packomania.com/
* My God, It’s Full of Dots! Posted on 27 September 2019 by Brian Hayes

# References

* ↑ Apollonian gasket
* ↑ mathforum : Problem of Apollonius
* ↑ Apollonius' Tangency Problem at MathPages
* ↑ Mandelbrot's Algorithm at Fractal Geometry from Yale University by Michael Frame, Benoit Mandelbrot, and Nial Neger
* ↑ Drawing 2D Apollonian gasket with n identical circles in Matlab by Guillaume JACQUENOT
* ↑ Apollonian Gasket in Mathematica and Povray by Paul Nylander
* ↑ Drawing the Apollonian Gasket with Common Lisp and Vecto by Luis Diego Fallas
* ↑ Leibnitz packing by Takaya Iwamoto with program in AutoLisp
* ↑ Apollonian Gasket - by Paul Bourke in BAsic and C
* ↑ How to pack n circles inside unit circle by Erich Friedman
* ↑ SVG Math Animation Example: Apollonian Gasket (-15,32,32,33) by KiHyuck Hong. See the src code.
* ↑ SVG Math Animation Example: Apollonian Gasket (-15,32,32,33) by KiHyuck Hong
* ↑ File Apolonian gasket containes about 8140 circles, but it looks like made of about 20 steps. So it should have about 10 460 353 205 circles
* ↑ Apollonian gasketin Haskell and Diagrams by Brent Yorgey
* ↑ Apollonian.hs - haskell code
* sage code
* Fractals and Steiner chains by Anders Sandberg with matlab code
* Looking through the Apollonian Window by Jerzy Kocik