Circle pack

Example of a circular packing in the plane

In mathematics , a circle packing is a collection of circles in the Euclidean plane or on any surface . Circle packings are examined with regard to their adjacencies and their geometry and play a role in the mathematical areas of graph theory and function theory .

The topic of spherical packing is clearly similar, but a separate area of ​​theory .

Terms

A planar graph and the corresponding circle packing

We call a set of circular disks in the Euclidean plane circular packing if the circular disks intersect in pairs at at most one point. A graph is a set of nodes and edges between nodes. The contact graph of a circle packing arises from the following construction: The graph contains a node for each circle. Two nodes are connected by an edge if the two circles in the plane touch. Two graphs are called isomorphic if we find a one-to-one relationship between the two graphs such that neighborhoods are preserved. ${\displaystyle G=(V,E)}$ ${\displaystyle V}$ ${\displaystyle E}$

The central question in the theory of circular packing is now: "Is there a circular packing for a given graph whose contact graph is isomorphic to ?" The KAT theorem (below) answers this question: There is such a circular packing if and only if is planar . This statement connects the geometric arrangement of the circles with the combinatorics of a graph. ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$

properties

Koebe-Andreev-Thurston theorem

The Koebe-Andreev-Thurston theorem (KAT theorem) or "circle packing theorem" states that every planar graph has a circle packing in the plane whose contact graph is isomorphic . ${\displaystyle G}$ ${\displaystyle G}$

The theorem is named after the three mathematicians Paul Koebe , EM Andreev and William P. Thurston . Koebe proved the theorem in 1936, but it was forgotten. Thurston rediscovered it in 1978 and noticed that it already followed from results from Andreev.

Uniqueness

In the course of the development of the KAT theorem, the uniqueness of the circular packing was also examined. Thurston himself made the observation: for a maximally planar graph, there is only one corresponding circle packing with the exception of Möbius transformations in the plane. If a graph has two corresponding circular packings, then there is a combination of translations, rotational extensions and inversions of the plane which converts the two circular packings into one another.

Mohar proved the uniqueness even for a larger class of graphs, the reduced maps .

Optimization problems

Circle packings motivate investigations of various optimization problems. This includes, for example, the optimal packing of circles in a circle or circles in a square or generally in a rectangle. Given a set of circles and a rectangle, the decision problem as to whether there is a packing of the circles in the rectangle is NP-complete .

Generalizations

One does not have to restrict oneself to the consideration of (disjoint) circle packings of circles in the plane. Various further questions are considered in mathematical research. These include, for example, the following: “Is there a corresponding circular packing on a surface other than the Euclidean plane for a given graph , e.g. B. in the projective plane or on a hyperbolic surface ? ”And“ What happens if the Euclidean metric is replaced by another? ”.

calculation

In addition to the existence and uniqueness of a circle packing for a given graph, a central question is the efficient computability. From the point of view of complexity theory, the exact calculation of a circle packing is NP-complete. Therefore, under the assumption ( P-NP problem ) there cannot be an efficient algorithm for the calculation. In practice, however, there are several approximation algorithms that can achieve sufficient accuracy. These include, for example, algorithms from Mohar and Stephenson. ${\displaystyle P\neq NP}$

Applications

The theory of circular packing is used in various areas of mathematics. This includes the calculation of optimal bounds for the separator problem in graph theory or the representation of algebraic groups .

Furthermore, the calculation of circle packings in the area of graph drawing can be used to create automated embedding of planar graphs. The existence of a cross-free embedding for a graph can be proven combinatorially efficient by a planarity test. However, an actual embedding in compliance with aesthetic requirements is challenging to design.

Brain scans

Circle packing is used to approximate analytical functions and describe conformal mappings . In medical technology, these functions are used to calculate a two-dimensional representation from three-dimensional data from the imaging process , which is easier to analyze. The circular packs help to maintain local structures.

origami

In the mathematical discipline of origami , the question of which three-dimensional figures can be folded from a sheet of paper without cuts and whether there is an algorithm that can provide folding instructions for any figure has long been open . In the 1980s this question was answered positively by Robert E. Lang and Toshiyuki Meguro together. The calculation of such a folding pattern uses circular packing. Each disjoint circle corresponds to an “extremity” of the object to be folded. Interconnected parts of the object are characterized by the adjacencies of the circles.

The origami folding patterns are used in art as well as in scientific and economic applications. This includes optimal folds for satellites and airbags .

literature

• Kenneth Stephenson: Introduction to Circle Packing: The Theory of Discrete Analytic Functions . Cambridge University Press, 2005.

Individual evidence

1. ^ William P. Thurston: The geometry and topology of three manifolds . 1978.
2. ↑ ^{a b} Bojan Mohar: A polynomial time circle packing algorithm . Elsevier, 1993, p. 257-263 .
3. ↑ Demaine, Fekete, Lang: Circle Packing for Origami Design Is Hard . 2010.
4. ↑ Bojan Mohar: Drawing Graphs in the Hyperbolic Plane . 1999, ISBN 978-3-540-46648-2 , pp. 127-136 .
5. ^ Miller, Teng, Thurston, Vavasis: Separators for sphere-packings and nearest neighbor graphs . 1997.
6. ^ Charles R. Collins and Kenneth Stephenson: A circle packing algorithm . 2003.
7. ^ Robert J. Lang: Mathematical Methods in Origami Design . 2009.