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.
Keywords: optimization, ball covering, heuristic algorithm, Chebyshev center, computational experiment
Received January 11, 2021
Revised February 20, 2021
Accepted February 25, 2021
Funding Agency: P.D.Lebedev’s research is supported by the Russian Science Foundation (project no. 19-11-00105).
Alexander Leonidovich Kazakov. Dr. Phys.-Math. Sci., Matrosov Institute for System Dynamics and Control Theory, Siberian Branch of the Russian Academy of Sciences, Irkutsk, 664033 Russia; Institute of Engineering Science of the Ural Branch of the Russian Academy of Sciences, Ekaterinburg 620049 Russia, e-mail: kazakov@icc.ru
Pavel Dmitrievich Lebedev, Cand. Phys.-Math. Sci., Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620108 Russia, e-mail: pleb@yandex.ru
REFERENCES
1. Kepler J. The six-cornered snowflake. Philadelphia: Paul Dry Books, 2010, 150 p. ISBN: 9781589882850 . Translated to Russian under the title O shestiugol’nykh snezhinkakh. Moscow: Nauka Publ., 1982, 192 p.
2. Preparata F.P., Shamos M.I. Computational geometry: An introduction. N Y: Springer-Verlag, 1985, 396 p. doi: 10.1007/978-1-4612-1098-6
3. Banhelyi B., Palatinus E., Levai B.L. Optimal circle covering problems and their applications. Central European J. Operations Research, 2015, vol. 23, no. 4, pp. 815–832. doi: 10.1007/s10100-014-0362-7
4. Shirokanev A.S., Kirsh D.V., Ilyasova N.Yu., Kupriyanov A.V. Investigation of algorithms for coagulate arrangement in fundus images. Computer Optics, 2018, vol. 42, no. 4, pp.712–721 (in Russian). doi: 10.18287/2412-6179-2018-42-4-712-721
5. Hayat H. et al. The state-of-the-art of sensors and environmental monitoring technologies in buildings. Sensors, 2019, vol. 19, no. 17, art.-no. 3648, 31 p. doi: 10.3390/s19173648
6. Bychkov I.V., Maksimkin N.N., Khozyainov I.S., Kiselev L.V. On the problem of patrolling the border of the water area guarded by a group of underwater vehicles. In: 5th All-Russian Sci. Tech. Conf. “Tekhnicheskie problemy osvoeniya Mirovogo okeana” (Technical problems of the development of the World Ocean), 2013, Vladivostok, Russia). Vladivostok: IPMT Publ., 2013, pp. 424–428. ISBN: 978-5-8044-1409-3 ,
7. Ershov A.A., Ushakov A.V., Ushakov V.N. An approach problem for a control system and a compact set in the phase space in the presence of phase constraints. Sb. Math., 2019, vol. 210, no. 8, pp. 1092–1128. doi: 10.1070/SM9141
8. Ushakov V.N., Ukhobotov V.I., Lipin A.E. An addition to the definition of a stable bridge and an approximating system of sets in differential games. Proc. Steklov Inst. Math., 2019, vol. 304, pp. 268–280. doi: 10.1134/S0081543819010206
9. Toth L.F. Regular figures. N Y: A Pergamon Press Book The Macmillan Co., 1964, 339 p. ISBN: 9780080100586 .
10. Toth L.F. Solid circle-packings and circle-coverings. Studia Sci. Math. Hungar., 1968, vol. 3, pp. 401–409.
11. Toth F.G. Covering the plane with two kinds of circles. Discrete & Computational Geometry, 1995, vol. 13, no. 3–4, pp. 445–457. doi: 10.1007/BF02574055
12. Florian A., Heppes A. Solid coverings of the Euclidean plane with incongruent circles. Discrete & Computational Geometry, 2000, vol. 23, no. 2, pp. 225–245. doi: 10.1007/PL00009497
13. Dorninger D. Thinnest covering of the Euclidean plane with incongruent circles. Anal. Geom. Metr. Spaces, 2017, vol. 5, no. 1, pp. 40–46. doi: 10.1515/agms-2017-0002
14. Banhelyi B., Palatinus E, Levai B.L. Optimal circle covering problems and their applications. Central European J. Operations Research, 2015, vol. 23, no. 4, pp. 815–832. doi: 10.1007/s10100-014-0362-7
15. Takhonov I.I. Multi-level regular coverings of the plane by disks. J. Math. Sci., 2015, vol. 211, no. 6, pp. 886–901. doi: 10.1007/s10958-015-2642-8
16. Kiseleva E.M., Lozovskaya L.I., Timoshenko E.V. Solution of continuous problems of optimal covering with spheres using optimal set-partition theory. Cybern. Syst. Anal., 2009, vol. 45, no. 3, pp. 421–437. doi: 10.1007/s10559-009-9113-5
17. Dumer I. Covering spheres with spheres. Discrete & Computational Geometry, 2006, vol. 38, no. 4, pp. 665–679. doi: 10.1007/s00454-007-9000-7
18. Kazakov A.L., Lebedev P.D. Algorithms of optimal packing construction for planar compact sets. Vychisl. Metody Programm., 2015, vol. 16, no. 2, pp. 307–317 (in Russian).
19. Lebedev P.D., Ushakov A.V. Approximating sets on a plane with optimal sets of circles. Autom. Remote Control, 2012, vol. 73, no. 3, pp. 485–493. doi: 10.1134/S0005117912030071
20. Kazakov A.L., Lebedev P.D. Algorithms for constructing optimal n-networks in metric spaces. Autom. Remote Control, 2017, vol. 78, no. 7, pp. 1290–1301. doi: 10.1134/S0005117917070104
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, 2020, vol. 31, pp. 18–33. doi: 10.26516/1997-7670.2020.31.18
22. Pshenichnyi B.N. Vypuklyi analiz i ekstremal’nye zadachi [Convex analysis and extremal problems]. Moscow: Nauka Publ., 1980, 320 p.
23. Garkavi A.L. On the Chebyshev center and convex hull of a set. Uspekhi Mat. Nauk., 1964, vol. 19, no. 6, pp. 139–145 (in Russian).
24. Shorikov A.F. An algorithm for a posteriori minimax estimation of states of discrete dynamic systems. I. Autom. Remote Control, 1996, vol. 57, no. 7, pp. 1016–1026.
25. Shorikov A.F. An algorithm for a posteriori minimax estimation of states of discrete dynamic systems. II. Autom. Remote Control, 1996, vol. 57, no. 9, pp. 1335–1343.
Cite this article as: P.D. Lebedev, A.L. Kazakov. Iterative algorithms for constructing the thinnest coverings of polyhedra by sets of different balls, Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2021, vol. 27, no. 1, pp. 116–129.
