Iterative methods for the construction of planar packings of circles of different size

P. D. Lebedev ; A. L. Kazakov

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 24 (2018) no. 2, pp. 141-151

Résumé

We consider the problem of constructing an optimal packing of a fixed number $n>1$ of circles, generally, of different radii in a planar compact set $M$. It is assumed that a positive number is given for each element of the packing such that the radius of the circle equals the product of this number by a parameter $r$, which is common to the whole package. The optimality criterion is the maximum of $r$, which leads, in particular, to an increase in the packing density, which is the ratio of the area of the packing to the area of $M$. In the proposed solution method, we iteratively change the coordinates of the centers of the packing elements $S_n$, which makes it possible to increase the radii of the circles. The developed computational procedures imitate the repulsion of the center of each element of the packing from nearby centers of other elements and from the boundary of $M$. We study the differential properties of a function of two variables $(x,y)$ whose value is the maximum radius of the circle of the packing centered at the point $(x,y)$, where the centers of the remaining elements are assumed to be fixed. The software implementation employs the notion of Chebyshev center of a compact set. A software complex is created and a number of examples are considered for sets $M$ of different geometry with the use of this complex. The results are visualized.

Détail

Keywords: circle packing problem (CPP), optimization, Chebyshev center, superdifferential, iterative algorithm.