We consider the problem of covering the surface of a three-dimensional set with a given number of elements when this set is a ball or a spherical segment and the covering elements are identical spherical caps. The optimization criterion is to minimize the radius of the spherical caps. This formulation is a relatively little-studied case of the classical circle covering problem (CCP) for a simply connected set, which is relevant in connection with applications in information and telecommunication technologies and logistics. The peculiarity of this study is that, besides the traditional Euclidean distance between points, a specific metric that characterizes the distance between points as the time of movement between them is also considered. A new heuristic algorithm is proposed, based on a spherical analog of the Voronoi diagram and the optical-geometrical analogy traditional for the authors, which allows solving the problem of covering non-planar surfaces. Since we could not find material for comparison with a general metric, the case of geodesic distance on a sphere was considered separately. For this case, we developed an algorithm for constructing the best covering based on finding the Chebyshev centers of Dirichlet zones, with a proof of the theorem that allows us to evaluate its effectiveness. Illustrative numerical calculations are performed.
Keywords: optimal covering, non-Euclidean distance, Voronoi diagram, optical-geometric analogy, Chebyshev center
Received October 30, 2023
Revised December 29, 2023
Accepted January 9, 2024
Funding Agency: The first author was supported by the Ministry of Education and Science of the Russian Federation within the project “Theoretical foundations, methods, and high-performance algorithms for continuous and discrete optimization to support interdisciplinary scientific research” (state registration no. 121041300065-9).
Anna Ananievna Lempert, Cand. Sci. (Phys.-Math.), Matrosov Institute for System Dynamics and Control Theory of the Siberian Branch of the Russian Academy of Sciences, Irkutsk, 664033 Russia, e-mail: lempert@icc.ru
Duc Minh Nguyen, doctoral student, Irkutsk National Research Technical University, Irkutsk, 664033 Russia, e-mail: nguyenducminh.mt@gmail.com
Pavel Dmitrievich Lebedev, Cand. Sci. (Phys.-Math.), Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620108 Russia, Ural Federal University, Yekaterinburg, 620000 Russia, e-mail: pleb@yandex.ru
REFERENCES
1. Krotov V.F., Piyavskii S.A. Sufficient optimality conditions in the problems of optimal coverage. Izvestiya Akad. Nauk SSSR. Tekhnicheskaia kibernetika, 1968, no. 2, pp. 10–17 (in Russian).
2. Toth L.F. Solid circle-packings and circle-coverings. Studia Sci. Math. Hungar., 1968, vol. 3, pp. 401–409.
3. Brusov V.S., Piyavskii S.A. A computational algorithm for optimally covering a plane region. USSR Comput. Math. Math. Phys., 1971, vol. 11, no. 2, pp. 17–27. doi: 10.1016/0041-5553(71)90161-3
4. Kazakov A.L., Lempert A.A. An approach to optimization in transport logistics. Autom. Remote Control, 2011, vol. 72, no. 7, pp. 1398–1404. doi: 10.1134/S0005117911070071
5. Mozhaev G.V. The problem of continuous observation of the Earth’s surface and cinematically correct satellite systems. Kosmicheskie issledovaniya, 1972, vol. 10, no. 6, pp. 833–840 (in Russian).
6. Piyavskii S.A. On network optimization. Izvestiya Akad. Nauk SSSR. Tekhnicheskaia kibernetika, 1968, no. 1, pp. 68–80 (in Russian).
7. Zikratov I.A., Shago F.N., Gurtov A.V., Ivaninskaya I.I. Optimization of the coverage zone for a cellular network based on mathematical programming. Nauch.-Tekh. Vestnik Inform. Tekh. Mekh. Optiki, 2015, vol. 15, no. 2, pp. 313–321 (in Russian). doi: 10.17586/2226-1494-2015-15-2-313-321
8. Kazakovtsev L.A., Gudyma M.N., Stupina A.A., Kirillov Yu.I. Problem of optimal location of wireless network equipment. Sovremennye Problemy Nauki i Obrazovaniya, 2013, no. 3, pp. 85–92 (in Russian).
9. Geniatulin K.A., Nosov V.I. Using of coordinating rings method in frequency-spatial planning of mobile satellite communication system with zonal maintenance. Vestnik Sib. Gos. Univ. Telekommun. Inform., 2014, no. 1, pp. 35–48 (in Russian).
10. Bychkov I.V., Kazakov A.L., Lempert A.A., Bukharov D.S., Stolbov A.B. An intelligent management system for the development of regional transport logistic infrastructure. Autom. Remote Control, 2016, vol. 77, no. 2, pp. 332–343. doi: 10.1134/S0005117916020090
11. Kazakovtsev L.A., Gudyma M.N. Statement of the problem of optimal placement of a network of air and water pollution monitoring sensors. Perspektivy Razvitiya Inform. Tekh., 2013, no. 13, pp. 19–24 (in Russian).
12. Heppes A., Melissen H. Covering a rectangle with equal circles. Period. Math. Hungar., 1997, vol. 34, no. 1–2, pp. 65–81. doi: 10.1023/A:1004224507766
13. Melissen J.B.M., Schuur P.C. Covering a rectangle with six and seven circles. Discrete Appl. Math., 2000, vol. 99, no. 1–3, pp. 149–156. doi: 10.1016/S0166-218X(99)00130-4
14. Nurmela K.J. Conjecturally optimal coverings of an equilateral triangle with up to 36 equal circles Experimental Math., 2000, vol. 9, no. 2, pp. 241–250. doi: 10.1080/10586458.2000.10504649
15. Nurmela K.J., Östergård P.R.J. Covering a square with up to 30 equal circles Helsinki Univ. of Technology — Research Reports, 2000, vol. 99, pp. 149–156.
16. Conway J.H., Sloane N.J.A. Sphere packing, lattices and groups. NY: Springer, 1999. 706 p. doi: 10.1007/978-1-4757-6568-7
17. Takhonov I.I. On some problems of covering the plane with circles. Diskret. Anal. Issled. Oper., 2014, vol. 21., no. 1, pp. 84–102 (in Russian).
18. Dorninger D. Thinnest covering of the Euclidean plane with incongruent circles. Analysis and Geometry in Metric Spaces, 2017, vol. 5, no. 1, pp. 40–46. doi: 10.1515/agms-2017-0002
19. Specht E. Packomania [e-resource]. Abailable on: http://www.packomania.com
20. Erich’s packing center [e-resource]. Abailable on: https://erich-friedman.github.io/packing/index.html
21. Joos A. Covering the 5-dimensional unit cube by eight congruent balls // Periodica Mathematica Hungarica volume. 2018. Vol. 77. P. 77–82. doi: 10.1007/s10998-018-0241-4 .
22. Bondarenko A., Prymak A., Radchenko D. Spherical coverings and X-raying convex bodies of constant width. Canad. Math. Bull., 2022, vol. 65, no. 4, pp. 860–866. doi: 10.4153/S0008439521001016
23. Stoyan Yu.G., Patsuk V.N. Method of covering of convex polyhedral set by minimal number of equal balls. Reports of the National Academy of Science of Ukraine, 2009, vol. 5, pp. 41–45.
24. Verger-Gaugry J.L. Covering a ball with smaller equal balls in $R^n$. Discrete Comput. Geom., 2005, vol. 33, no. 1, pp. 143–155. doi: 10.1007/s00454-004-2916-2
25. Dumer I. Covering spheres with spheres. Discrete Comput. Geom., 2007, vol. 38, no. 4, pp. 665–679. doi: 10.1007/s00454-007-9000-7
26. Bezdek A., Fodor F., Vigh V., Zarnocz T. On the multiplicity of arrangements of congruent zones on the sphere [e-resource]. 2023, 11 p. Available on: https://arxiv.org/abs/1705.02172 .
27. Galiev Sh.I. Multiple packings and coverings of a sphere. Discrete Math. Appl., 1996, vol. 6, no. 4, pp. 413–426. doi: 10.1515/dma.1996.6.4.413
28. Kazakov A., Lempert A., Lebedev P. Congruent circles packing and covering problems for multiconnected domains with non-euclidean metric, and their applications to logistics. In: (eds.) Yu.I. Shokin, H. Milosevic, D.V. Esipov. Proc. Int. Conf. Mathematical and Information Technologies (MIT-2016), CEUR Workshop Proceedings, 2017, vol. 1839, pp. 334–343. Available on: https://ceur-ws.org/Vol-1839/MIT2016-p30.pdf
29. 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
30. Kazakov A.L., Lempert A.A., Bukharov D.S. On segmenting logistical zones for servicing continuously developed consumers. Autom. Remote Control, 2013, vol. 74, no. 6, pp. 968–977. doi: 10.1134/S0005117913060076
31. Feynman R.P., Leighton R.B., Sands M. Feynman lectures on physics. Volume 3: quantum mechanics. NY, Basic Books, 2011, 395 p. ISBN: 978-0465025015 . Translated to Russian under the title Feinmanovskie lektsii po fizike. Tom 3: Izluchenie. Volny. Kvanty, Moscow, Librokom, 2013, 242 p.
32. Fortune S. A sweepline algorithm for Voronoi diagrams. Algorithmica, 1987, no. 1–4, vol. 2, pp. 153–174. doi: 10.1007/BF01840357
33. Shkaberina G., Verenev L., Tovbis E., Rezova N., Kazakovtsev L. Clustering algorithm with a greedy agglomerative heuristic and special distance measures. Algorithms, 2022, vol. 15, no. 6, pp. 191. doi: 10.3390/a15060191
34. Lebedev P. Program for calculating the optimal hemisphere coverage by a set of spherical segments. Registered Rospatent Certificate No. 2015661543 dated 10.29.2015 (in Russian).
35. Arestov V.V., Babenko A.G. On Delsarte scheme of estimating the contact numbers. Proc. Steklov Inst. Math., 1997, vol. 219, pp. 36–65.
36. Stepanov N.N. Sfericheskaya trigonometriya [Spherical trigonometry]. Leningrad, Moscow, Gos. Tekh. Izdat., 1948, 154 p.
37. Ushakov V.N., Lakhtin A.S., Lebedev P.D. Optimization of the Hausdorff distance between sets in Euclidean space. Proc. Steklov Inst. Math., 2015, vol. 291, suppl. 1, pp. 222–238. doi: 10.1134/S0081543815090151
Cite this article as: A.A. Lempert, P.D. Lebedev, D.M. Nguyen. On the problem of covering spherical figures with equal spherical caps. Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2024, vol. 30, no. 1, pp. 142–155.
