The paper addresses the thinnest (suboptimal) covering problem for a part of a circular cylinder surface with a finite number of equal circles in the intrinsic geometry of the surface. We introduce generalized Chebyshev center and Dirichlet cell notions adapted to the cylindrical metric. We prove that for a sufficiently small generalized radius of a compact set, the Chebyshev center is unique. An estimate is obtained for the decrease of the covering radius when moving the circle centers to their corresponding Chebyshev centers. Based on this estimate, we construct an iterative algorithm and prove a theorem on the monotonic decrease of the covering radius, which guarantees convergence of the algorithm to a locally optimal solution. A reduction of the Chebyshev center search on the cylinder to a planar problem with periodic extension is proposed. Numerical experiments confirm the algorithm’s efficiency; the obtained coverings show high density for the studied configurations. Comparison with a known heuristic algorithm demonstrates improvement. The results are applicable to sensor location on cylindrical structures and to cylindrical three-dimensional printing technologies.
Keywords: suboptimal covering, cylinder, Dirichlet cell, Chebyshev center, geodesic curve
Received April 10, 2026
Revised April 28, 2026
Accepted May 04, 2026
Funding Agency: A.A.Lempert’s research is funded by the Ministry of Science and Higher Education of the Russian Federation (No. of registration: 126021217232-3).
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, e-mail: kazakov@icc.ru
Pavel Dmitrievich Lebedev, Cand. Sci (Phys.-Math.), Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences, Yekaterinburg, ul. S. Kovalevskoi, 16, 620077, box 82, Russia, e-mail: pleb@yandex.ru
Anna Ananievna Lempert, Cand. Sci (Phys.-Math.), Matrosov Institute for System Dynamics and Control Theory, Siberian Branch of the Russian Academy of Sciences, Irkutsk, 664033 Russia, e-mail: lempert@icc.ru
REFERENCES
1. Barbashin E.A., Tabueva V.A. Dynamicheskie systemy s tsilindricheskim fazovym prostranstvom [Dynamical systems with the cylindrical phase space]. Moscow, Nauka Publ., 1969, 299 p.
2. Ammari H.M. Theory and practice of wireless sensor networks: cover, sense, and inform. Cham, Springer, 2023, 762 p. https://doi.org/10.1007/978-3-031-07823-1
3. Kazakovtsev L.A., Gudyma M.N., Stupina A.A., Kirillov Yu.I. Problem of optimal location of wireless network equipment. Sovr. Probl. Nauki i obraz., 2013, no. 3, 8 p. (in Russian)
4. Miklush V.A., Tatarnikova T.M. Problem solution of different sensors location in organizing a mesh topology wireless sensor network. J. Achievements of Modern Radioelectr., 2022, vol. 76, no. 12, pp. 15–20 (in Russian). https://doi.org/10.18127/j20700784-202212-03
5. Zhao D., Ruan K., Zhang G., Wang Y., Chen Z., Zha X., Dong K., Xiong Y. Supportless cylindrical printing of rotating components with overhangs on a rotary FDM 3D printer. In: Tan J., Liu Y., Huang HZ., Yu J., Wang Z. (eds.) Advances in Mechanical Design. ICMD 2023, ser. Mechanisms and Machine Science, vol. 155, Singapore, Springer, 2023, pp. 2099–2117. https://doi.org/10.1007/978-981-97-0922-9_133
6. Yigit I.E., Khan S.A., Lazoglu I. Robotic additive turning with a novel cylindrical slicing method. Inter. J. Adv. Manuf. Tech., 2022, vol. 119, pp. 7641–7651. https://doi.org/10.1007/s00170-021-08567-1
7. Zhang X., Cui W., Li W., Liou F. Effects of tool path in remanufacturing cylindrical components by laser metal deposition. Inter. J. Adv. Manuf. Tech., 2019, vol. 100, pp. 1607–1617. https://doi.org/10.1007/s00170-018-2786-z
8. Gritskevich O.V., Meshcheryakov N.A., Pod’yanol’skiy Yu.V. Formation of an optical image of arbitrary geometric shape on curved surfaces of revolution. Avtometriya, 1997, no. 2, pp. 26–33 (in Russian).
9. Tóth L.F. Lagerungen in der ebene, auf der kugel und im raum. Berlin, Heidelberg, Springer, 1953, 198 p. https://doi.org/10.1007/978-3-662-01206-2 . Translated to Russian under the title Raspolozheniya na ploskosti, na sfere i v prostranstve, Moscow, Fizmatlit Publ., 1958, 363 p.
10. Hardin D.P., Saff E.B. Discretizing manifolds via minimum energy points. Notices Amer. Math. Soc., 2004, vol. 51, no. 10, pp. 1186–1194.
11. Ushakov V.N., Lebedev P.D. Algorithms of optimal set covering on the planar $\mathbb{R}^2$. Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki, 2016, vol. 26, iss. 2, pp. 258–270 (in Russian). https://doi.org/10.20537/vm160212
12. Kazakov A.L., Lebedev P.D. Algorithms of optimal packing construction for planar compact sets. Vych. Met. Programm., 2015, vol. 16, no. 2, pp. 307–317 (in Russian).
13. Kazakov A.L., Lebedev P.D. Algorithms for constructing optimal n-networks in metric spaces. Autom. Remote Control, 2017, vol. 78, iss. 7, pp. 1290–1301. https://doi.org/10.1134/S0005117917070104
14. Lempert A.A., Kazakov A.L., Bukharov D.S. Mathematical model and program system for solving a problem of logistic objects placement. Autom. Remote Control, 2015, vol. 76, no. 8, pp. 1463–1470. https://doi.org/10.1134/S0005117915080111
15. Bleicher M.N., Tóth L.F. Circle packing and circle covering on a cylinder. Michigan Math. J., 1964, vol. 11, pp. 337–341. https://doi.org/10.1307/mmj/1028999186
16. Hifi M., M’Hallah R. A literature review on circle and sphere packing problems: models and methodologies. Adv. Oper. Res., 2009, vol. 2009. Art. ID 150624, 22 p. https://doi.org/10.1155/2009/150624
17. Kazakov A.L., Lempert A.A., Nguyen D.M. On covering of cylindrical and conical surfaces with equal balls. Bull. Irkutsk State Univer. Ser. Math., 2024, vol. 48, pp. 34–48. https://doi.org/10.26516/1997-7670.2024.48.34
18. Brusov V.S., Piyavskii S.A. A computational algorithm for optimally covering a plane region. Comput. Math. Math. Phys., 1971, vol. 11, iss. 2, pp. 17—27. https://doi.org/10.1016/0041-5553(71)90161-3
19. Garkavi A.L. On the Chebyshev center and convex hull of a set. Uspekhi Mat. Nauk, 1964, vol. 19, no. 6(120), pp. 139–145 (in Russian).
20. Sypchenko I.V., Timonina D.S. Closed geodesics on piecewise smooth surfaces of revolution with constant curvature. Sb. Math., 2015, vol. 206, iss. 5, pp. 738–769. https://doi.org/10.1070/SM2015v206n05ABEH004477
21. 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, part 2, pp. 1016–1026.
22. Botkin N.D., Turova-Botkina V.L. An algorithm for finding the Chebyshev center of a convex polyhedron. Appl. Math. Optim., 1994, vol. 29, pp. 211–222. https://doi.org/10.1007/BF01204183
23. Nguyen D.M. Matematicheskiye modeli i algoritmy resheniya zadach o pokrytii i upakovke dlya poverkhnostey vrashcheniya [Mathematical models and algorithms for solving problems of covering and packing for surfaces of revolution]. Candidate Sci. (Phys.-Math.) Dissertation, Irkutsk, Irkutskii Gos. Univer., 2025, 176 p.
24. Tóth G., Tóth L., Kuperberg W. Miscellaneous problems about packing and covering. In: Lagerungen. Grundlehren der Math. Wissenschaften, vol. 360. Cham, Springer, 2023, pp. 313–336. https://doi.org/10.1007/978-3-031-21800-2_16
Cite this article as: A.L. Kazakov, P.D. Lebedev, A.A. Lempert. Constructing suboptimal coverings of a circular cylinder with equal geodesic circles. Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2026, vol. 32, no. 3, pp. 96–109.
