Communications in Information and Systems
Volume 18 (2018)
An approximate method for circle packing and disc covering
Pages: 73 – 89
Circle packing is to optimize the arrangement of circles (of equal or varying sizes) on a given domain with the maximal packing density such that no overlapping occurs. As an NP-hard problem, it is scientifically challenging so that no procedure is able to exactly solve the problem in deterministic polynomial time even for the Euclidean domains. In this paper, we develop an approximate method for packing a large number of circles (of similar sizes). In contrast to the existing methods that use nonlinear optimization with carefully designed strategies to deal with complex boundaries, our methods are purely geometrical and highly intuitive. Observing that circle packing is closely related to disc covering, we formulate both problems in a centroidal Voronoi tessellation (CVT)-like computational framework and show that a locally optimal solution to the covering (resp. packing) problem can be obtained by iteratively updating the centers of the circumscribed (resp. inscribed) circles of the Voronoi cells. Using geodesic exponential map, we can compute those centers efficiently on manifold triangle meshes, hereby extending our 2D algorithm to non-Euclidean domains. Experimental results on synthetic and real-world models demonstrate the efficacy of our method.
This work is partially supported by the NSF of China (61772016, 61772312), China 973 Program (2015CB352502), and the key research and development project of Shandong province (2017GGX10110).
Published 17 October 2018