𑁍

Discrete Comput Geom (2010) 44: 487–507 DOI 10.1007/s00454-009-9216-9 Irreducible Apollonian Configurations and Packings Steve Butler · Ron Graham · Gerhard Guettler · Colin Mallows Received: 18 January 2009 / Revised: 20 July 2009 / Accepted: 20 July 2009 / Published online: 1 August 2009 © The Author(s) 2009. This article is published with open access at Springerlink.com Abstract An Apollonian configuration of circles is a collection of circles in the plane with disjoint interiors such that the complement of the interiors of the circles consists of curvilinear triangles. One well-studied method of forming an Apollonian configu- ration is to start with three mutually tangent circles and fill a curvilinear triangle with a new circle, then repeat with each newly created curvilinear triangle. More generally, we can start with three mutually tangent circles and a rule (or rules) for how to fill a curvilinear triangle with circles. In this paper we consider the basic building blocks of these rules, irreducible Apol- lonian configurations. Our main result is to show how to find a small field that can realize such a configuration and also give a method to relate the bends of the new circles to the bends of the circles forming the curvilinear triangle. Keywords Irreducible · Apollonian · Packing · Eulerian · Inversion S. Butler supported by an NSF Postdoctoral fellowship. S. Butler UCLA, Los Angeles, USA e-mail: [email protected] R. Graham () UCSD, San Diego, USA e-mail: [email protected] G. Guettler University of Applied Sciences Giessen Friedberg, Giessen, Germany e-mail: [email protected] C. Mallows Avaya Labs, Basking Ridge, NJ, USA e-mail: [email protected] 488 Discrete Comput Geom (2010) 44: 487–507 1 Introduction An Apollonian configuration of circles is a collection of circles in the plane with disjoint interiors such that the complement of the interiors of the circles consists of curvilinear triangles. Such configurations have been studied before as special cases of circle packing (see [11, 12]). In examining these configurations it is often more convenient to consider the bend of the circle (one over the radius) than the radius itself. Perhaps the most well-known, and most studied, example of an Apollonian con- figuration is formed by starting with three mutually tangent circles and then filling in each curvilinear triangle with the unique circle which is tangent to all three sides of that triangle (see Fig. 1a); we then repeat this process with each newly created curvilinear triangle as often as desired. This has the remarkable property that if the first three circles have integer bends a, b, c and 〈a, b, c〉 := ab + ac + bc is also the square of an integer, then each new circle which is added will also have integer bend. Further, for any three mutually tangent circles with bends d, e, f then 〈d, e, f 〉 = m2 for m an integer. These are consequences of Descartes Circle Theo- rem. The properties of this configuration have been extensively studied (see [4–7]). However, there are other ways to fill in a curvilinear triangle. Recently Guettler and Mallows [8] examined the case where the curvilinear triangle is filled by three new circles, each tangent to exactly two sides (see Fig. 1b). This also has a similar property in that if the first three circles have integer bends a, b, c and 〈a, b, c〉 = 2m2 for m an integer, then each new circle will also have integer bend. Further, for any three mutually tangent circles with bends d, e, f then 〈d, e, f 〉 = 2m2 for m an integer. (This additional factor of 2 plays an important role in the packing, as we will see in Sect. 3.) In both of these cases the important element of the packing is the recursive rule for filling in the curvilinear triangles. The basic building blocks for forming these rules are the irreducible Apollonian configurations which we will introduce in Sect. 2. In Fig. 1 Two rules for packing a curvilinear triangle Discrete Comput Geom (2010) 44: 487–507 489 Sect. 3 we will look at the problem of determining a small field that can be used to represent a configuration (irreducible or not). In Sect. 4 we will show how to take an Apollonian configuration and construct a rule for filling a curvilinear triangle. In Sect. 5 we give some concluding remarks. 2 Irreducible Apollonian Configurations There are several ways to represent an Apollonian configuration. Combinatorially it can be represented as a tangency graph where each circle is a vertex and tangent circles are joined by an edge. The resulting graph is a planar triangulated graph, which corresponds to a triangulation of the sphere. Theorem 1 (Koebe–Andreev–Thurston [11]) Given a triangulation of the sphere, there exists an essentially unique circle packing where circles correspond to vertices and edges to tangency between circles. Moreover, by projection this can be realized as a circle packing in the plane, and any two circle packings in the plane corresponding to the triangulated graph differ by a Moebius transformation. In Fig. 2a we give a planar triangulated graph. One circle packing in the plane that realizes this configuration is shown in Fig. 2b (the outer circle has negative bend, so its interior lies on the outside of the disc). There are of course many possible ways to realize the configuration by transforming the packing using a Moebius transforma- tion. We will see that when looking for a small field that can be used to represent the packing, an important type of packing is one where we have a unit circle centered at (0, 0) and two circles with bend 0 located at y = 1 and y = −1. We will call such a packing a standard packing. One standard packing for Fig. 2a is shown in Fig. 2c. Every packing can be transformed into a standard packing by inverting at a circle centered at a point of tangency, then rotating, scaling, and translating to put it into the correct position. In general, standard packings are not unique, since by choosing to invert at a different point of tangency we will be led to a (possibly) different standard packing. However, since there are only finitely many points of tangency, there are only finitely many standard packings. By using V −E +F = 2 we have the following. Fig. 2 Different representations of an Apollonian packing 490 Discrete Comput Geom (2010) 44: 487–507 Fig. 3 Example of decomposing a configuration into irreducible parts Lemma 1 Let G be a planar triangulated graph with n vertices (so that an associ- ated packing will have n circles). Then there are at most 3n − 6 different standard packings with tangency graph G. In this paper we will focus on irreducible Apollonian configurations. In terms of the tangency graph, this corresponds to having no triangles that are not faces. In terms of a packing, this is equivalent to saying that no proper subset of circles is also a nontrivial Apollonian configuration (trivial means three mutually tangent circles). Starting with a tangency graph, if we have a triangle which is not a face, we can decompose the graph into two parts: the triangle with the interior vertices and edges; and the triangle with the exterior vertices and edges. We can continue doing this until each graph is irreducible, or in other words, we can decompose the tangency graph into irreducible components which are glued together on triangular faces. We can do the analogous procedure for the packing in that we can break it into irreducible packings that are glued together on three circles. An example of this is shown in Fig. 3, where we have a packing which is not irreducible and then show the two irreducible components in the packing. So when we want to study properties of Apollonian packings, we can focus on the building blocks which are the irreducible components of the packing. There are many such irreducible Apollonian configuration with n circles. Starting with n = 4, there are (1, 0, 1, 1, 2, 4, 10, 25, 87, 313, 1357, 6244, 30926, 158428, . . .) such con- figurations (see A007021 in [10], which differs in the n = 5 case; also see [1]). 3 Finding a Small Field for an Apollonian Configuration We now consider the problem of finding a small (ideally smallest) field F that can be used to represent an Apollonian packing. Here to represent a packing we mean that the bends and the centers of the circles can be expressed using elements of the field F, as described below. If we compare the two different packings mentioned in the introduction, we see that one of them satisfies 〈a, b, c〉 = m2 , while the other satisfies 〈a, b, c〉 = 2m2 . This factor of 2 in the second case plays an important role in the packing. In general we will say that a packing over a field F is a q-packing, for some fixed q ∈ F, if the Discrete Comput Geom (2010) 44: 487–507 491 bends of all the circles are in F and further any three mutually tangent circles with bends a, b, c satisfy 〈a, b, c〉 = qm2 for some m in F. Note that for every packing, by enlarging the field (i.e., F = R) we can ensure that the packing is a 1-packing. The interesting cases are where for some field, q is not a square. Examples are given in some of the figures below where q is not a square. In our packing we can represent every circle by the triple (√qx, y; b) where (√qx, y) is the center and b is the bend. The tangency relationship between two circles with nonzero bend translates into the equation q(x1 − x2)2 + (y1 − y2)2 = ( 1 b1

• 1 b2 )2 . A circle with bend 0 (which corresponds to a straight line in the diagram) would be described by (∞, ∞; 0). This does not uniquely describe the line. So in this case we will represent the circle by the line y = √qmx + b or x = √qa; equivalently we have that the line passes through two points of the form (√qx1, y1) and (√qx2, y2). (For most of this paper, we will see that we can assume that it is of the form y = b.) The tangency relationship between a circle (√qx0, y0; b0) and the circle y = √qmx + b then becomes qm2 + 1 b2 0 = (y0 − qmx0 − b)2