Numerical methods for the construction of packings of different balls into convex compact sets

P. D. Lebedev ; A. L. Kazakov ; A. A. Lempert

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 26 (2020) no. 2, pp. 173-187

Résumé

The problem of an optimal packing of incongruent balls into a convex compact set is studied. We consider sets of balls whose radii are proportional to a specified parameter $r$. The aim is to maximize $r$. The maximum possible number of different types of balls is three. The problem belongs to the class of NP-hard problems and is solved numerically. We propose algorithms based on partitioning the given compact set into zones of influence of the centers of the elements (generalized Dirichlet zones). The partition is constructed using the optical-geometric approach developed by the authors earlier. A preliminary result is obtained and then improved by a geometric algorithm based on a step-by-step shift of points aimed at maximizing the radius of the current ball. To find the shift direction, we construct the superdifferential of the function equal to the maximum radius of a packed ball centered at the current point. We derive a formula for the maximum growth direction of this function. The developed algorithms are implemented as a software complex for the construction of a ball packing of a compact set. A numerical experiment was carried out for several examples. Packings with balls of different radii are constructed for containers of different shapes: a cube, a sphere, and a cylinder.

Détail

Keywords: packing, sphere, optimization, generalized Dirichlet zone, directional derivative, superdifferential, optical-geometric approach.