Iterative algorithms for constructing the thinnest coverings of convex polyhedra by sets of different balls

P. D. Lebedev ; A. L. Kazakov

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 27 (2021) no. 1, pp. 116-129

Résumé

In control theory and various areas of applied mathematics, it is important to approximate sets of complex geometry by unions of simple unified bodies. One of the most common methods here is covering sets with balls. In the classical statement, all the balls are equal; nevertheless, a more general statement is also of interest when the balls can be different. In this paper, we study the problem of constructing a covering of a compact set $M$ in three-dimensional Euclidean space by a set of a given number of balls whose radii are equal to the product of a common parameter $r$ and an individual positive coefficient. The optimality criterion is the minimum of $r$. We propose heuristic algorithms for constructing such coverings based on splitting the set $M$ into zones of influence of points and finding their Chebyshev centers. Statements about the properties of these algorithms are proved, and the algorithms are implemented. The problems of covering a cube with different sets of balls of two types are solved numerically. Possible directions of further research are outlined and discussed.

Détail

Keywords: optimization, ball covering, Chebyshev center, computational experiment.
Mots-clés : heuristic algorithm

Bibliographie

[1] Kepler I., O shestiugolnykh snezhinkakh, per. s latinskogo Yu. A. Danilova, Nauka, M., 1982, 192 pp.

[2] Preparata F.P., Shamos M.I., Computational geometry: An Introduction, Springer-Verlag, N Y, 1985, 396 pp. | MR

[3] Banhelyi B., Palatinus E., Levai B.L., “Optimal circle covering problems and their applications”, Central European J. Operations Research, 23:4 (2015), 815–832 | DOI | MR | Zbl

[4] Shirokanev A.S., Kirsh D.V., Ilyasova N.Yu., Kupriyanov A.V., “Issledovanie algoritmov rasstanovki koagulyatov na izobrazhenie glaznogo dna”, Kompyuternaya optika, 42:4 (2018), 712–721 | DOI

[5] Hayat H. et al, “The State-of-the-art of sensors and environmental monitoring technologies in buildings”, Sensors, 19:17 (2019), 3648, 31 pp. | DOI

[6] Bychkov I.V., Maksimkin N.N., Khozyainov I.S., Kiselev L.V., “O zadache patrulirovaniya granitsy akvatorii, okhranyaemoi gruppoi podvodnykh apparatov”, Tekhnicheskie problemy osvoeniya Mirovogo okeana, 5 (2013), 424–428

[7] Ershov A.A., Ushakov A.V., Ushakov V.N., “Zadacha o sblizhenii upravlyaemoi sistemy s kompaktom v fazovom prostranstve pri nalichii fazovykh ogranichenii”, Mat. sb., 210:8 (2019), 29–66 | DOI | MR | Zbl

[8] Ushakov V.N., Ukhobotov V.I., Lipin A.E., “Ob odnom dopolnenii k opredeleniyu stabilnogo mosta i approksimiruyuschei sistemy mnozhestv v differentsialnykh igrakh”, Tr. MIAN, 304 (2019), 285–297 | DOI | Zbl

[9] Toth L.F., Regular figures, A Pergamon Press Book The Macmillan Co., N Y, 1964, 339 pp. | MR | Zbl

[10] Toth L.F., “Solid circle-packings and circle-coverings”, Studia Sci. Math. Hungar., 3 (1968), 401–409 | MR | Zbl

[11] Toth F.G., “Covering the plane with two kinds of circles”, Discrete Computational Geometry, 13:3–4 (1995), 445–457 | DOI | MR | Zbl

[12] Florian A., Heppes A., “Solid Coverings of the Euclidean Plane with Incongruent Circles”, Discrete Computational Geometry, 23:2 (2000), 225–245 | DOI | MR | Zbl

[13] Dorninger D., “Thinnest covering of the Euclidean plane with incongruent circles”, Anal. Geom. Metr. Spaces, 5:1 (2017), 40–46 | DOI | MR | Zbl

[14] Banhelyi B., Palatinus E, Levai B.L., “Optimal circle covering problems and their applications”, Central European J. Operations Research, 23:4 (2015), 815–832 | DOI | MR | Zbl

[15] Takhonov I.I., “Multi-level regular coverings of the plane by disks”, J. Math. Sci., 211:6 (2015), 886–901 | DOI | MR

[16] Kiseleva E.M., Lozovskaya L.I., Timoshenko E.V., “Reshenie nepreryvnykh zadach optimalnogo pokrytiya sharami s ispolzovaniem teorii optimalnogo razbieniya mnozhestv”, Kibernetika i sistemnyi analiz, 2009, no. 3, 98–117 | Zbl

[17] Dumer I., “Covering spheres with spheres”, Discrete Computational Geometry, 38:4 (2006), 665–679 | DOI | MR

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

[19] Lebedev P.D., Ushakov A.V., “Approksimatsiya mnozhestv na ploskosti optimalnymi naborami krugov”, Avtomatika i telemekhanika, 2012, no. 3, 79–90 | Zbl

[20] Kazakov A.L., Lebedev P.D., “Algoritmy postroeniya nailuchshikh n-setei v metricheskikh prostranstvakh”, Avtomatika i telemekhanika, 2017, no. 7, 141–155 | Zbl

[21] Kazakov A., Lebedev P., Lempert A., “On covering bounded sets by collections of circles of various radii”, The Bulletin of Irkutsk State University. Ser.: Mathematics, 31 (2020), 18–33 | DOI | MR | Zbl

[22] Pshenichnyi B.N., Vypuklyi analiz i ekstremalnye zadachi, Nauka, M., 1980, 320 pp. | MR

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

[24] Shorikov A.F., “Algoritm resheniya zadachi aposteriornogo minimaksnogo otsenivaniya sostoyanii diskretnykh dinamicheskikh sistem. I”, Avtomatika i telemekhanika, 1996, no. 7, 130–143 | Zbl

[25] Shorikov A.F., “Algoritm resheniya zadachi aposteriornogo minimaksnogo otsenivaniya sostoyanii diskretnykh dinamicheskikh sistem. II”, Avtomatika i telemekhanika, 1996, no. 9, 139–150 | Zbl