A linearized circle packing algorithm

作者：Orick Gerald L; Stephenson Kenneth^*; Collins Charles

来源：Computational Geometry-Theory and Applications, 2017, 64: 13-29.

DOI：10.1016/j.comgeo.2017.03.002

• Circle packing
• Tutte embedding
• Sparse linear system

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 (R) 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.

• 出版日期2017-8