Geodesic
Numerical methods for constructing suboptimal~packings of~nonconvex domains with~curved~boundary
Diskretnyj analiz i issledovanie operacij, Tome 27 (2020) no. 4, pp. 58-79

Voir la notice de l'article provenant de la source Math-Net.Ru

We study the problem of constructing some optimal packings of simply-connected nonconvex plane domains with a union of congruent circles. We consider the minimization of the radius of circles if the number of the circles is fixed. Using subdifferential calculus, we develop theoretical methods for solution of the problem and propose an approach for constructing some suboptimal packings close to optimal. In the numerical algorithms, we use the iterative procedures and take into account mainly the location of the current center of a packing element, the centers of the nearest neighboring elements, and the points of the boundary of the domain. The algorithms use the same supergradient ascent scheme whose parameters can be adapted to the number of packing elements and the geometry of the domain. We present a new software package whose efficiency is demonstrated by several examples of numerical construction of some suboptimal packings of the nonconvex domains bounded by the Cassini oval, a hypotrochoid, and a cardioid. Illustr. 6, bibliogr. 37.
Keywords: packing, maximization, optimization, algorithm, numerical procedure, directional derivative, superdifferential, approximation, supergradient ascent. 
@article{DA_2020_27_4_a2,
     author = {P. D. Lebedev and V. N. Ushakov and A. A. Uspenskii},
     title = {Numerical methods for constructing suboptimal~packings of~nonconvex domains with~curved~boundary},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {58--79},
     publisher = {mathdoc},
     volume = {27},
     number = {4},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2020_27_4_a2/}
}
TY  - JOUR
AU  - P. D. Lebedev
AU  - V. N. Ushakov
AU  - A. A. Uspenskii
TI  - Numerical methods for constructing suboptimal~packings of~nonconvex domains with~curved~boundary
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2020
SP  - 58
EP  - 79
VL  - 27
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2020_27_4_a2/
LA  - ru
ID  - DA_2020_27_4_a2
ER  - 
%0 Journal Article
%A P. D. Lebedev
%A V. N. Ushakov
%A A. A. Uspenskii
%T Numerical methods for constructing suboptimal~packings of~nonconvex domains with~curved~boundary
%J Diskretnyj analiz i issledovanie operacij
%D 2020
%P 58-79
%V 27
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2020_27_4_a2/
%G ru
%F DA_2020_27_4_a2
P. D. Lebedev; V. N. Ushakov; A. A. Uspenskii. Numerical methods for constructing suboptimal~packings of~nonconvex domains with~curved~boundary. Diskretnyj analiz i issledovanie operacij, Tome 27 (2020) no. 4, pp. 58-79. http://geodesic.mathdoc.fr/item/DA_2020_27_4_a2/