Geodesic
Iterative methods for the construction of planar packings of circles of different size
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 24 (2018) no. 2, pp. 141-151 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

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.
Keywords: circle packing problem (CPP), optimization, Chebyshev center, superdifferential, iterative algorithm. 
@article{TIMM_2018_24_2_a12,
     author = {P. D. Lebedev and A. L. Kazakov},
     title = {Iterative methods for the construction of planar packings of circles of different size},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {141--151},
     year = {2018},
     volume = {24},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2018_24_2_a12/}
}
TY  - JOUR
AU  - P. D. Lebedev
AU  - A. L. Kazakov
TI  - Iterative methods for the construction of planar packings of circles of different size
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2018
SP  - 141
EP  - 151
VL  - 24
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/TIMM_2018_24_2_a12/
LA  - ru
ID  - TIMM_2018_24_2_a12
ER  - 
%0 Journal Article
%A P. D. Lebedev
%A A. L. Kazakov
%T Iterative methods for the construction of planar packings of circles of different size
%J Trudy Instituta matematiki i mehaniki
%D 2018
%P 141-151
%V 24
%N 2
%U http://geodesic.mathdoc.fr/item/TIMM_2018_24_2_a12/
%G ru
%F TIMM_2018_24_2_a12
P. D. Lebedev; A. L. Kazakov. Iterative methods for the construction of planar packings of circles of different size. Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 24 (2018) no. 2, pp. 141-151. http://geodesic.mathdoc.fr/item/TIMM_2018_24_2_a12/

[1] Krasovskii N.N., Subbotin A.I., Pozitsionnye differentsialnye igry, Nauka, M., 1974, 456 pp. | MR

[2] Conway J., Sloane N., Sphere packing. Lattices and groups, Springer Science and Business Media, N Y, 1999, 706 pp. | DOI | MR

[3] Hifi M., M'Hallah R., “A literature review on circle and sphere packing problems: Models and methodologies”, Advances Oper. Research, 2009 (2009), 1–22 | DOI

[4] Kazakov A.L., Lempert A.A., “Ob odnom podkhode k resheniyu zadach optimizatsii, voznikayuschikh v transportnoi logistike”, Avtomatika i telemekhanika, 2011, no. 7, 50–57 | Zbl

[5] Kazakov A., Lempert A., “On mathematical models for optimization problem of logistics infrastructure”, Intern. J. of Artificial Intelligence, 13:1 (2015), 200–210

[6] Kazakov A.L., Lebedev P.D., “Algoritmy postroeniya optimalnykh upakovok dlya kompaktnykh mnozhestv na ploskosti”, Vychislit. metody i programmirovanie, 16:3 (2015), 307–317

[7] Lebedev P.D., Uspenskii A.A., “Algoritmy postroeniya optimalnykh upakovok v trekhmernom evklidovom prostranstve”, Modern Problems in Math. and its Appl., Proc. 47th Intern. Youth School-Conf. (Yekaterinburg), CEUR Workshop Proc., 1662, 2016, 84–93

[8] Yaskov G.N., “Metod resheniya zadachi upakovki raznykh krugov s vyborom perspektivnykh nachalnykh tochek”, Zbirnik naukovikh prats Kharkivskogo natsionalnogo universitetu Povitryanikh Sil, 2010, no. 3(25), 119–122 | MR

[9] Lopez C., Beasley J., “A formulation space search heuristic for packing unequal circles in a fixed size circular container”, European J. Oper. Research, 251:1, 64–73 | DOI | MR | Zbl

[10] Kubach T., Bortfeldt A., Gehring H., “Parallel greedy algorithms for packing unequal circles into a strip or a rectangle”, Central European J. Oper. Research, 17:4 (2009), 461–477 | DOI | MR | Zbl

[11] Zeng Z., Yu X., Chen M., Liu Yu., “A memetic algorithm to pack unequal circles into a square”, Comput. Oper. Research, 92 (2018), 47–55 | DOI | MR | Zbl

[12] Kazakov A.L., Lempert A.A., Le Q.M., “An Algorithm for packing circles of two types in a fixed size container with non-euclidean metric”, CEUR Workshop Proc., 1975 (2017), 286–297

[13] Subbotin A.I., Obobschennye resheniya uravnenii v chastnykh proizvodnykh pervogo poryadka. Perspektivy dinamicheskoi optimizatsii, In-t kompyuternykh tekhnologii, M.; Izhevsk, 2003, 336 pp.

[14] Demyanov V.F., Vasilev L.V., Nedifferentsiruemaya optimizatsiya, Nauka, M., 1981, 384 pp. | MR

[15] Demyanov V.F., Rubinov A.M., Osnovy negladkogo analiza i kvazidifferentsialnoe ischislenie, Nauka, M., 1990, 432 pp. | MR

[16] Sukharev A.G., Timokhov A.V., Fedorov V.V., Kurs metodov optimizatsii, Nauka, M., 1986, 326 pp. | MR

[17] Leikhtveis K., Vypuklye mnozhestva, Nauka, M., 1985, 335 pp. | MR

[18] Garkavi A.L., “O chebyshevskom tsentre i vypukloi obolochke mnozhestva”, Uspekhi mat. nauk, 19:6 (1964), 139–145 | MR | Zbl

[19] Tot L. F., Raspolozheniya na ploskosti, na sfere i v prostranstve, Gos. izd-vo fiz.-mat. lit., M., 1958, 365 pp.