Packing Disks by Flipping and Flowing
- PDF / 616,592 Bytes
- 24 Pages / 439.37 x 666.142 pts Page_size
- 10 Downloads / 231 Views
Packing Disks by Flipping and Flowing Robert Connelly1 · Steven J. Gortler2 Received: 11 November 2019 / Revised: 27 May 2020 / Accepted: 4 August 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract We provide a new type of proof for the Koebe–Andreev–Thurston (KAT) planar circle packing theorem based on combinatorial edge-flips. In particular, we show that starting from a disk packing with a maximal planar contact graph G, one can remove any flippable edge e− of this graph and then continuously flow the disks in the plane, so that at the end of the flow, one obtains a new disk packing whose contact graph is the graph resulting from flipping the edge e− in G. This flow is parameterized by a single inversive distance. Keywords Circle packing · Rigidity · Inversive distance Mathematics Subject Classification 52C26
1 Introduction The well known Koebe–Andreev–Thurston (KAT) (planar) circle packing theorem states that for every planar graph G with n vertices, there is a corresponding packing of n disks (with mutually disjoint interiors) in the plane, whose contact graph is isomorphic to G. Moreover, if G is maximal (i.e., all faces triangular), then this packing is unique up to Möbius transformations and reflections [2,19,33]. This theorem is important in conformal geometry [27] and has been generalized in numerous directions
Editor in Charge: János Pach R. Connelly: Partially supported by NSF Grant DMS-1564493. S. J. Gortler: Partially supported by NSF Grant DMS-1564473. Robert Connelly [email protected] Steven J. Gortler [email protected] 1
Department of Mathematics, Cornell University, Ithaca, USA
2
School of Engineering and Applied Sciences, Harvard University, Cambridge, USA
123
Discrete & Computational Geometry
[26,30,33]. In [14], a packing whose graph is a triangulation of the plane is called a compact packing. There are a variety of techniques that have been used to establish the KAT theorem. These include methods based on conformal geometry [19], combinatorial analysis of hyperbolic polyhedra [2,28], circle geometry, cone-singularities and topology of continuous maps [24,33], variational methods [3,9,26], iterative "flattening" algorithms [10,25,32], and combinatorial Ricci flow [8]. In this paper, we present a novel simple and constructive approach for proving the KAT circle packing theorem based on ideas from (local) rigidity theory [6,13]. We start with any "trilaterated" packing; such a packing is constructed by starting with three fixed disks in mutual tangential contact, and then adding in, one-by-one, new disks that are tangential to three previously placed disks. It will be easy to establish that such a packing is unique up to Möbius transformation and reflection. (See Fig. 3.) Next, we use the fact that one can always combinatorially transform any maximal planar graph to any desired target maximal planar graph G using a finite sequence of combinatorial "edge flips" [4,31,34]. (See Fig. 4.) Then, at the heart of this paper, we show how we can continuously flow t
Data Loading...
