Circle Packing Explorations

Year: 2013 Authors: Francesco De Comité

Core claim

Combining Apollonian gaskets, Steiner chains, circle inversion, and Möbius transformations yields an open-ended family of compact circle-pack design images.

Topics

circle packing, geometric transformation, recursive pattern generation, experimental mathematics

Domains

discrete geometry, complex analysis, inversive geometry, graphical algorithms, generative art, visual design, mathematical imagery, algorithmic aesthetics

Methods

Apollonian gasket recursion, Steiner chain construction, circle inversion, Möbius transformation

Media

digital images, computer-generated patterns, tablet application

Paper text

The text below is the locally extracted OCR/Markdown version of the paper. Raw PDF files remain local and are not published here.

Page 1

Proceedings of Bridges 2013: Mathematics, Music, Art, Architecture, Culture

Circle Packing Explorations

Francesco De Comité Laboratoire d’Informatique Fondamentale de Lille University of Sciences and Technology of Lille France Francesco.De-Comite@univ-lille1.fr

Abstract

Circle packing can be seen as the art of placing tangent circles on the plane, leaving as little unoccupied space as possible. Circle packing is a very attractive field of mathematics, from several points of view. It contains interesting and complex questions, both mathematical and algorithmical, and keeps its properties through a wide range of geometric transformations. There are several ways to obtain and modify circle packing structures, giving rise to an infinity of patterns.

A Two Step Process

Circle packing has been (re)introduced by William Thurston [5] in 1985. Kenneth Stephenson developed its study in [4]. The goal of this paper is to show how one can use different ways of producing circle packings, together with different geometric transformations that preserves the tangency property of the arrangement, in order to produce elegant and appealing images. Generating pictures of a circle packing can be separated in two phases: first generate a circle packing structure, then modify this structure while preserving the tangency property. For sake of aesthetical homogeneity, we will only consider packings of tangent circles included in one external circle, also part of the tangency pattern. At Bridges 2012, Inlis and Kaplan [1] presented a method to produce fractal circular rings of tangent circles, where spaces are filled with Apollonian circles. Their algorithm shares some similarity with ours, but is in some ways more restrictive.

Generating Sets of Tangent Circles

Apollonian Gaskets

Apollonian gaskets are obtained by recursively filling the gaps between three tangent circles with a circle tangent to all those three circles. The mathematics tools used to solve the problem are known since René Descartes, and were re-discovered by Frederick Soddy, who published his solution in 1936 in the form of a poem in Nature [3]. Computing Apollonian gaskets is an interesting and not so difficult programming exercise. Basic Apollonian gaskets leave large portions of the plane empty: the interior of the initial circles. By filling each of those empty circles with new initial circles, and calling the algorithm again, one can obtain a more compact and very attractive packing (figure 1). Another way for generating different designs is not to limit oneself to four initial inner circles, but generalize the process to $n+1$ inner circles (figure 2). Or you can choose, at each level of recursion, randomly or not, how many circles to start with (figure 3).

399

Page 2

De Comité

Figure 1: A standard Apollonian gasket (left), and three of its avatars with two, three and seven levels of recursion. Note the emergence of the Sierpinski triangle in the last iteration.

Figure 2: A recursive gasket with $7+1$ initial circles

Figure 3: Gasket with randomly filled circles

Steiner Chains

Steiner chains are chains of tangent circles, each of those circles also tangent to two fixed and non-intersecting circles. Steiner chains are obtained by first constructing the easy solution: n circles forming a chain between two concentric circles, then using a circle inversion to distort the arrangement. This is also very easy to program. As for Apollonian gaskets, one can recursively fill new inner circles with new Steiner chains. In this case, it is the space between tangent circles that remains empty. One can use the Apollonian gasket algorithm to fill those spaces. The algorithm for compact circle packing generation becomes then: “Each time you define a new circle, fill it with a Steiner chain and fill the spaces between it and circles tangent to it with the Apollonian gasket algorithm”. A lot of parameters can be tuned, opening a new infinite range of possible designs (figures 4 and 5).

Figure 4: Mixing chains and gaskets.

Figure 5: Mixing chains and gaskets

Page 3

Circle Packing Explorations

Transforming Circle Packings

To generate even more different designs, one can apply to the set of tangent circles one or more geometric transformations that preserve the tangency property. Two such transformations are easy to program: circle inversion and Möbius transformation. Those transformations share some common properties, but programming them as separate objects provides different ways to access their parameters.

Circle Inversion

A circle inversion is defined by the circle of center $O$ and radius $r$ . The inverse of point $P$ with respect to this circle is point $P^{\prime }$ , lying on the line passing through $O$ et $P$ , such that $OP\times O{P}^{\prime }=r^2$

Circle inversions map circles to circles, and preserve tangency. (In some hidden way, circle inversion was already used in the preceding step, for generating irregular Steiner chains). Since circle inversions turn the whole geometric plane inside out, one can play with colors: the bicolor pattern in the second and third row of figure 8 comes from initially faraway circles, which are projected near the center of the inversion circle.

Figure 6: Generation+geometric transformations

Figure 7: Generation+geometric transformations

Möbius Transformation

A Möbius transformation is a function of a complex variable $z$ defined by:

$a,b,c,d$ are complex numbers satisfying $ad-bc\ne 0$ . A complete exploration of the graphical potentialities of Möbius transformations can be found in Mumford’s Indra’s Pearls [2].

Möbius transformations distort the whole design, giving the curved pattern visible in figure 7 and in the fourth line of figure 8.

Conclusion

Having solved consistently the individual algorithmical problems (gaskets, Steiner chains, transformations), it is not difficult to combine them in different ways, then observe the result and play with parameters. With some luck, new and interesting patterns emerge. Adding some interactivity, involving a lot more people in the experiments, could speed the process of exploring the universe of experimental maths, computing and visualisation. A tablet application would be of great help…

Page 4

De Comité

Figure 8: A catalog of circle packings

References

[1] Tiffany C. Inglis and Craig S. Kaplan. Circle patterns in gothic architecture. In Robert Bosch, Douglas McKenna, and Reza Sarhangi, editors, Proceedings of Bridges 2012: Mathematics, Music, Art, Architecture, Culture, pages 133-140, Phoenix, Arizona, USA, 2012. Tessellations Publishing. [2] David Mumford, Caroline Series, and David Wright. Indra’s Pearls: the Vision of Felix Klein. Cambridge Univ. Press, Cambridge, 2002. [3] Frederick Soddy. The Kiss Precise. Nature, 137:1021, 1936. [4] Kenneth Stephenson. Introduction to Circle Packing. The Theory of Discrete Analytic Functions. Cambridge Univ. Press, Cambridge, 2005. [5] William Thurston. The Finite Riemann Mapping Theorem, 1985. Invited talk, Purdue University.