On the problem of covering spherical figures with equal spherical caps

A. A. Lempert ; P. D. Lebedev ; D. Nguyen

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 30 (2024) no. 1, pp. 142-155

Résumé

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.

Détail

Keywords: optimal covering, Voronoi diagram, optical-geometric analogy, Chebyshev center.
Mots-clés : non-Euclidean distance

Bibliographie

[1] Krotov V.F., Piyavskii S.A., “Dostatochnye usloviya optimalnosti v zadachakh ob optimalnykh pokrytiyakh”, Izv. AN SSSR. Tekhnicheskaya kibernetika, 1968, no. 2, 10–17

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

[3] Brusov V.S., Piyavskii S.A., “Vychislitelnyi algoritm optimalnogo pokrytiya oblastei ploskosti”, Zhurn. vychisl. matematiki i mat. fiziki, 11:2 (1971), 304–313

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

[5] Mozhaev G.V., “Zadacha o nepreryvnom obzore poverkhnosti Zemli i kinematicheski pravilnye sputnikovye sistemy”, Kosmicheskie issledovaniya, 10:6 (1972), 833–840

[6] Piyavskii S.A., “Ob optimizatsii setei”, Izv. AN SSSR. Tekhnicheskaya kibernetika, 1968, no. 1, 68–80 | Zbl

[7] Zikratova I.A., Shago F.N., Gurtov A.V., Ivaninskaya I.I., “Optimizatsiya zony pokrytiya seti sotovoi svyazi na osnove matematicheskogo programmirovaniya”, Nauch.-tekhn. vestn. inform. tekhnologii, mekhaniki i optiki, 15:2 (2015), 313–321 | DOI | MR

[8] Kazakovtsev L.A., Gudyma M.N., Stupina A.A., Kirillov Yu.I., “Zadacha vybora optimalnogo razmescheniya elementov besprovodnoi seti”, Sovremennye problemy nauki i obrazovaniya, 2013, no. 3, 85–92 | MR

[9] Geniatulin K.A., Nosov V.I., “Primenenie metoda koordinatsionnykh kolets pri chastotno-territorialnom planirovanii sistemy sputnikovoi svyazi s zonalnym obsluzhivaniem”, Vestn. SibGUTI, 2014, no. 1, 35–45

[10] Bychkov I.V., Kazakov A.L., Lempert A.A. i dr., “Intellektnaya sistema upravleniya razvitiem transportno-logisticheskoi infrastrukturoi regiona”, Problemy upravleniya, 1 (2014), 27–35

[11] Kazakovtsev L.A., Gudyma M.N., “Postanovka zadachi optimalnogo razmescheniya seti datchikov monitoringa zagryazneniya vozdukha i vody”, Perspektivy razvitiya informatsionnykh tekhnologii, 2013, no. 13, 19–24

[12] Heppes A., Melissen H., “Covering a rectangle with equal circles”, Period. Math. Hungar, 34 (1977), 65–81 | DOI | MR

[13] Melissen J.B.M., Schuur P.C., “Covering a rectangle with six and seven circles”, Discret. Appl. Math., 99 (2000), 149–156 | DOI | MR | Zbl

[14] Nurmela K.J., “Conjecturally optimal coverings of an equilateral triangle with up to 36 equal circles”, Experimental Math., 9:2 (2000), 241–250 | DOI | MR | Zbl

[15] Nurmela K.J., Ostergard P.R.J., “Covering a square with up to 30 equal circles”, Helsinki University of Technology — Research Reports, 99 (2000), 149–156

[16] Conway J.H., Sloane N.J.A., Sphere Packing. Lattices and Groups, Springer, NY, 1999, 706 pp. | DOI | MR

[17] Takhonov I.I., “O nekotorykh zadachakh pokrytiya ploskosti krugami”, Diskret. analiz i issledovanie operatsii, 21:1 (2014), 84–102 | MR | Zbl

[18] Dorninger D., “Thinnest covering of the Euclidean plane with incongruent circles”, Analysis and Geometry in Metric Spaces, 5 (2017), 40–46 | DOI | MR | Zbl

[19] Specht E., Packomania [e-resource] URL: http://www.packomania.com

[20] Erich's Packing Center [e-resource] URL: 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, 77 (2018), 77–82 | DOI | MR | Zbl

[22] Bondarenko A., Prymak A., Radchenko D., “Spherical coverings and X-raying convex bodies of constant width”, Canad. Math. Bull., 65 (2021), 1–7 | MR

[23] Stoyan Yu.G., Patsuk V.N., “Metod pokrytiya vypuklogo mnogogrannogo mnozhestva minimalnym kolichestvom odinakovykh sharov”, Reports of the National Acad. Sci. Ukraine, 5 (2009), 41–45 | Zbl

[24] Verger-Gaugry J.L., “Covering a ball with smaller equal balls in $R^n$”, Discrete Computational Geometry, 33:1 (2005), 143–155 | DOI | MR | Zbl

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

[26] Bezdek A., Fodor F., Vigh V., Zarnocz T., On the multiplicity of arrangements of congruent zones on the sphere, [e-resource], 2023, 11 pp., arXiv: 1705.02172

[27] Galiev Sh.I., “Mnogokratnye upakovki i pokrytiya sfery”, Diskret. matematika, 8:3 (1996), 148–160 | DOI | Zbl

[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”, Proc. Int. Conf. Mathematical and Information Technologies (MIT-2016), CEUR Workshop Proceedings, 1839, eds. Yu. I. Shokin, H. Milosevic, D. V. Esipov, 2017, 334–343 URL: https://ceur-ws.org/Vol-1839/MIT2016-p30.pdf

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

[30] Kazakov A.L., Lempert A.A., Bukharov D.S., “K voprosu o segmentatsii logisticheskikh zon dlya obsluzhivaniya nepreryvno raspredelennykh potrebitelei”, Avtomatika i telemekhanika, 2013, no. 6, 87–100 | Zbl

[31] Feinman R., Leiton R., Sends M., Feinmanovskie lektsii po fizike, v. 3, Izluchenie. Volny. Kvanty, Librokom, M., 2013, 243 pp.

[32] Fortune S., “A sweepline algorithm for Voronoi diagrams”, Algorithmica, 2 (1987), 153–174 | DOI | MR | Zbl

[33] Shkaberina G., Verenev L., Tovbis E., Rezova N., Kazakovtsev L., “Clustering algorithm with a greedy agglomerative heuristic and special distance measures”, Algorithms, 15:6 (2022), 191 | DOI

[34] Lebedev P.D., Programma vychisleniya optimalnogo pokrytiya polusfery naborom sfericheskikh segmentov, Programma dlya EVM. Registr. nomer 2015661543. Data registratsii 29.10.2015

[35] Arestov V.V., Babenko A.G., “O skheme Delsarta otsenki kontaktnykh chisel”, Tr. MIAN, 219 (1997), 44–73 | Zbl

[36] Stepanov N.N., Sfericheskaya trigonometriya, OGIZ, L.; M., 1948, 154 pp.

[37] Ushakov V.N., Lakhtin A.S., Lebedev P.D., “Optimizatsiya khausdorfora rasstoyaniya mezhdu mnozhestvami v evklidovom prostranstve”, Tr. In-ta matematiki i mekhaniki UrO RAN, 20:3 (2014), 291–308