×

zbMATH — the first resource for mathematics

A linearized circle packing algorithm. (English) Zbl 1371.65021
Summary: This paper presents a geometric algorithm for approximating radii and centers for a variety of univalent circle packings, including maximal circle packings on the unit disc and the sphere and certain polygonal circle packings in the plane. This method involves an iterative process which alternates between estimates of circle radii and locations of circle centers. The algorithm employs sparse linear systems and in practice achieves a consistent linear convergence rate that is far superior to traditional packing methods. It is deployed in a MATLAB\(^{\circledR}\) package which is freely available. This paper gives background on circle packing, a description of the linearized algorithm, illustrations of its use, sample performance data, and remaining challenges.
MSC:
65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
52C15 Packing and covering in \(2\) dimensions (aspects of discrete geometry)
03B40 Combinatory logic and lambda calculus
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bannister, Michael J.; Devanny, William E.; Eppstein, David; Goodrich, Michael T., The Galois complexity of graph drawing: why numerical solutions are ubiquitous for force-directed, spectral, and circle packing drawings, J. Graph Algorithms Appl., 19, 2, 619-656, (2015) · Zbl 1328.05128
[2] Bauer, David; Stephenson, Kenneth; Wegert, Elias, Circle packings as differentiable manifolds, Contrib. Algebra Geom., 53, 399-420, (2012), published on-line December 2011 · Zbl 1258.52011
[3] Bobenko, Alexander I.; Springborn, Boris A., Variational principles for circle patterns and Koebe’s theorem, Trans. Am. Math. Soc., 356, 659-689, (2003) · Zbl 1044.52009
[4] Philip L. Bowers, Kenneth Stephenson, Conformal tilings II: local isomorphism, hierarchy, and conformal type, preprint. · Zbl 1364.52013
[5] Bowers, Philip L.; Stephenson, Kenneth, Uniformizing dessins and belyĭ maps via circle packing, Mem. Am. Math. Soc, 170, 805, (2004) · Zbl 1080.52511
[6] Bowers, Philip L.; Stephenson, Kenneth, A “regular” pentagonal tiling of the plane, Conform. Geom. Dyn., 1, 58-86, (1997) · Zbl 0883.05034
[7] Bowers, Philip L.; Stephenson, Kenneth, Conformal tilings I: foundations, theory, and practice, Conform. Geom. Dyn., 21, 1-63, (2017) · Zbl 1364.52013
[8] Cannon, James W.; Floyd, W. J.; Parry, Walter, Finite subdivision rules, Conform. Geom. Dyn., 5, 153-196, (2001) · Zbl 1060.20037
[9] Collins, Charles R.; Driscoll, Tobin A.; Stephenson, Kenneth, Curvature flow in conformal mapping, Comput. Methods Funct. Theory, 3, 1, 325-347, (2003) · Zbl 1073.52511
[10] Collins, Charles R.; Stephenson, Kenneth, A circle packing algorithm, Comput. Geom. Theory Appl., 25, 233-256, (2003) · Zbl 1023.52005
[11] Orick, Gerald; Stephenson, Kenneth; Collins, Chuck, matlab^® package, (2016)
[12] Colin de Verdière, Yves, Empilements de cercles: convergence d’une méthode de point fixe, Forum Math., 1, 395-402, (1989) · Zbl 0685.52012
[13] Doyle, Peter G.; Laurie Snell, J., Random walks and electric networks, Carus Math. Monogr., vol. 22, (1984), Math. Assoc. Amer. · Zbl 0583.60065
[14] Dubejko, Tomasz, Recurrent random walks, Liouville’s theorem, and circle packings, Math. Proc. Camb. Philos. Soc., 121, 3, 531-546, (1997) · Zbl 0888.30005
[15] Godsil, Chris; Royle, Gordon, Algebraic graph theory, Grad. Texts Math., vol. 207, (2001), Springer · Zbl 0968.05002
[16] Grantab, Rassin; Shenoy, Vivek B.; Ruoff, Rodney S., Anomalous strength characteristics of tilt grain boundaries in graphene, Science, 330, 946-948, (2010)
[17] Ori, Gurel-Gurevich; Nachmias, Asaf, Recurrence of planar graph limits, Ann. Math., 177, 761-781, (2013) · Zbl 1262.05031
[18] Hoste, Jim; Thistlethwaite, Morwen, Knotscape, (1998), Software package
[19] Hurdal, Monica K.; Stephenson, Ken, Cortical cartography using the discrete conformal approach of circle packings, NeuroImage, 23, Supplement 1, S119-S128, (2004)
[20] Somer, Frank L.; Canright, G. S.; Kaplan, Theodore; Chen, Kun; Mostoller, Mark, Inherent structures and two-stage melting in two dimensions, Phys. Rev. Lett., 79, 3431, (1997)
[21] Lee Orick, Gerald, Computational circle packing: geometry and discrete analytic function theory, (2010), Univ. of Tenn, directed by Ken Stephenson
[22] Kenyon, Richard; Okounkov, Andrei, Limit shapes and the complex Burgers equation, Acta Math., 199, 2, 263-302, (2007), preprint, 1996 · Zbl 1156.14029
[23] Lam, Miu-Ling; Liu, Yun-Hui, Sensor network deployment using circle packings, (Information Networking: Towards Ubiquitous Networking and Services, Lect. Notes Comput. Sci., vol. 5200, (2008), Springer), 385-395
[24] Miller, Gary L.; Thurston, William, Separators in two and three dimensions, (Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, (May 1990), ACM Baltimore), 300-309
[25] Mohar, Bojan, A polynomial time circle packing algorithm, Discrete Math., 117, 257-263, (1993) · Zbl 0785.52006
[26] Mohar, Bojan, Circle packings of maps in polynomial time, Eur. J. Comb., 18, 785-805, (1997) · Zbl 0891.52008
[27] Pinkall, Ulrich; Polthier, Konrad, Computing discrete minimal surfaces and their conjugates, Exp. Math., 2, 15-36, (1993) · Zbl 0799.53008
[28] Rodin, Burt; Sullivan, Dennis, The convergence of circle packings to the Riemann mapping, J. Differ. Geom., 26, 349-360, (1987) · Zbl 0694.30006
[29] Rohde, Steffen; Gill, James T., On the Riemann surface type of random planar maps, Rev. Mat. Iberoam., 29, 1071-1090, (2013) · Zbl 1275.30007
[30] Schramm, Oded, Circle patterns with the combinatorics of the square grid, Duke Math. J., 86, 347-389, (1997) · Zbl 1053.30525
[31] Sheffield, Scott, Quantum gravity and inventory accumulation, (2011), preprint · Zbl 1359.60120
[32] Sheffield, Scott; Duplantier, Bertrand, Liouville quantum gravity and KPZ, (2010), preprint · Zbl 1226.81241
[33] Stephenson, Kenneth, software, (1992)
[34] Stephenson, Kenneth, A probabilistic proof of Thurston’s conjecture on circle packings, Rend. Semin. Mat. Fis. Milano, LXVI, 201-291, (1996) · Zbl 0997.60504
[35] Stephenson, Kenneth, Introduction to circle packing: the theory of discrete analytic functions, (2005), Camb. Univ. Press New York, (QA640.7.S74) · Zbl 1074.52008
[36] William Thurston, The finite Riemann mapping theorem, in: An International Symposium at Purdue University in celebrations of de Branges’ proof of the Bieberbach conjecture, March 1985 (Invited talk).
[37] Tutte, W. T., How to draw a graph, Proc. Lond. Math. Soc., 13, 38, 743-767, (1963) · Zbl 0115.40805
[38] Wegert, Elias; Roth, Oliver; Kraus, Daniela, On Beurling’s boundary value problem in circle packing, Complex Var. Elliptic Equ., 57, 397-410, (2012) · Zbl 1241.30012
[39] Werness, Brent, Discrete analytic functions on non-uniform lattices without global geometric control
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.