×

zbMATH — the first resource for mathematics

A circle packing algorithm. (English) Zbl 1023.52005
Summary: A circle packing is a configuration \(P\) of circles realizing a specified pattern of tangencies. Radii of packings in the euclidean and hyperbolic planes may be computed using an iterative process suggested by William Thurston.
We describe an efficient implementation, discuss its performance, and illustrate recent applications. A central role is played by new and subtle monotonicity results for “flowers” of circles.

MSC:
52C26 Circle packings and discrete conformal geometry
52C15 Packing and covering in \(2\) dimensions (aspects of discrete geometry)
05B40 Combinatorial aspects of packing and covering
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] R. Barnard, G.B. Williams, Combinatorial excursions in moduli space, Pacific J. Math., to appear · Zbl 1066.52024
[2] Beardon, A.F.; Stephenson, K., The uniformization theorem for circle packings, Indiana univ. math. J., 39, 1383-1425, (1990) · Zbl 0797.30008
[3] Beardon, A.F.; Stephenson, K., The schwarz – pick lemma for circle packings, illinois, J. math., 35, 577-606, (1991) · Zbl 0753.30016
[4] Benjamini, I.; Schramm, O., Harmonic functions on planar and almost planar graphs and manifolds, via circle packings, Invent. math., 126, 565-587, (1996) · Zbl 0868.31008
[5] Bowers, P.L., The upper Perron method for labelled complexes with applications to circle packings, Proc. Cambridge phil. soc., 114, 321-345, (1993) · Zbl 0795.30037
[6] P.L. Bowers, K. Stephenson, Uniformizing dessins and Belyı̆ maps via circle packing, Preprint · Zbl 1080.52511
[7] Bowers, P.L.; Stephenson, K., Circle packings in surfaces of finite type: an in situ approach with applications to moduli, Topology, 32, 157-183, (1993) · Zbl 0783.30030
[8] Bowers, P.L.; Stephenson, K., A branched andreev – thurston theorem for circle packings of the sphere, Proc. London math. soc. (3), 73, 185-215, (1996) · Zbl 0856.51012
[9] Bowers, P.L.; Stephenson, K., A “regular” pentagonal tiling of the plane, Conformal geometry and dynamics, 1, 58-86, (1997) · Zbl 0883.05034
[10] Brooks, R., Circle packings and co-compact extensions of Kleinian groups, Invent. math., 86, 461-469, (1986) · Zbl 0578.30037
[11] de Verdière, Y.C., Une principe variationnel pour LES empilements de cercles, Invent. math., 104, 655-669, (1991) · Zbl 0745.52010
[12] T. Dubejko, Branched circle packings, discrete complex polynomials, and the approximation of analytic functions, PhD thesis, University of Tennessee (advisor: Ken Stephenson), 1993
[13] Dubejko, T., Branched circle packings and discrete Blaschke products, Trans. amer. math. soc., 347, 4073-4103, (1995) · Zbl 0849.30028
[14] Dubejko, T.; Stephenson, K., The branched Schwarz lemma: A classical result via circle packing, Michigan math. J., 42, 211-234, (1995) · Zbl 0865.30034
[15] Dubejko, T.; Stephenson, K., Circle packing: experiments in discrete analytic function theory, Experimental math., 4, 307-348, (1995) · Zbl 0853.52019
[16] He, Z.-X.; Rodin, B., Convergence of circle packings of finite valence to Riemann mappings, Comm. anal. geom., 1, 31-41, (1993) · Zbl 0777.30003
[17] He, Z.-X.; Schramm, O., Inverse Riemann mapping theorem for relative circle domains, Pacific J. math., 171, 157-165, (1995) · Zbl 0860.30005
[18] He, Z.-X.; Schramm, O., On the convergence of circle packings to the Riemann map, Invent. math., 125, 285-305, (1996) · Zbl 0868.30010
[19] He, Z.-X.; Schramm, O., The c∞-convergence of hexagonal disk packings to the Riemann map, Acta math., 180, 219-245, (1998) · Zbl 0913.30004
[20] Hodgson, C.D.; Rivin, I., A characterization of compact convex polyhedra in hyperbolic 3-space, Invent. math., 111, 77-111, (1993) · Zbl 0784.52013
[21] Hurdal, M.K.; Bowers, P.L.; Stephenson, K.; Sumners, D.W.L.; Rehm, K.; Schaper, K.; Rottenberg, D.A., Quasi-conformally flat mapping the human cerebellum, (), 279-286
[22] Cannon, J.W.; Floyd, W.J.; Parry, W., Finite subdivision rules, Conformal geometry and dynamics, 5, 153-196, (2001) · Zbl 1060.20037
[23] Koebe, Kontaktprobleme der konformen abbildung, Ber. Sächs. akad. wiss. Leipzig, math.-phys. kl., 88, 141-164, (1936) · Zbl 0017.21701
[24] Miller, G.L.; Thurston, W., Separators in two and three dimensions, (), 300-309
[25] Mohar, B., A polynomial time circle packing algorithm, Discrete math., 117, 257-263, (1993) · Zbl 0785.52006
[26] Morgan, W., On Thurston’s uniformization theorem for three-dimensional manifolds, (), 37-126
[27] Rodin, B., Schwarz’s lemma for circle packings, Invent. math., 89, 271-289, (1987) · Zbl 0634.30009
[28] Rodin, B., Schwarz’s lemma for circle packings II, J. differential geom., 30, 539-554, (1989) · Zbl 0646.30014
[29] Rodin, B.; Sullivan, D., The convergence of circle packings to the Riemann mapping, J. differential geom., 26, 349-360, (1987) · Zbl 0694.30006
[30] ()
[31] K. Stephenson, Circle packing and discrete analytic function theory, in: R. Kühnau (Ed.), Handbook of Complex Analysis, Vol. 1, Elsevier, Amsterdam, to appear · Zbl 1067.30086
[32] Stephenson, K., A probabilistic proof of Thurston’s conjecture on circle packings, Rendiconti del seminario mate. e fisico di milano, LXVI, 201-291, (1996) · Zbl 0997.60504
[33] Stephenson, K., Approximation of conformal structures via circle packing, (), 551-582 · Zbl 0932.30001
[34] W. Thurston, The Geometry and Topology of 3-Manifolds, Princeton University Notes, Preprint · Zbl 0483.57007
[35] W. Thurston, The finite Riemann mapping theorem, 1985. Invited talk, An International Symposium at Purdue University on the occasion of the proof of the Bieberbach conjecture, March 1985
[36] van Eeuwen, J., The discrete schwarz – pick lemma for overlapping circles, Pams, 121, 1087-1091, (1994) · Zbl 0808.30016
[37] G.B. Williams, Discrete conformal welding, PhD thesis, University of Tennessee, Knoxville 1999 (advisor: Ken Stephenson) · Zbl 1056.30016
[38] Williams, G.B., Earthquakes and circle packings, J. anal. math., 85, 371-396, (2001) · Zbl 1059.30039
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.