рус eng
«THE BULLETIN OF IRKUTSK STATE UNIVERSITY». SERIES «MATHEMATICS»
«IZVESTIYA IRKUTSKOGO GOSUDARSTVENNOGO UNIVERSITETA». SERIYA «MATEMATIKA»
ISSN 1997-7670 (Print)
ISSN 2541-8785 (Online)

List of issues > Series «Mathematics». 2024. Vol 48

On Covering of Cylindrical and Conical Surfaces with Equal Balls

Author(s)
Alexander L. Kazakov1,2, Anna A. Lempert1, Duc Minh Nguyen2

1Matrosov Institute for System Dynamics and Control Theory SB RAS, Irkutsk, Russian Federation

2Irkutsk National Research Technical University, Irkutsk, Russian Federation

Abstract
The article concerns the problem of covering the lateral surface of a right circular cylinder or a cone with equal balls. The surface is required to belong to their union, and the balls’ radius is minimal. The centers of the balls must lie on the covered surface. The problem is relevant for mathematics and for applications since it arises in security and communications. We develop heuristic algorithms for covering construction based on a geodesic Voronoi diagram. The construction of a covering is a non-trivial task since the line of intersection of a cylinder or a cone with a sphere is a closed curve of the fourth order. To compare the numerical results with the known ones, we unroll the surface of revolution onto a plane. Another feature is that, we use both Euclidean distance and a special non-Euclidean metric, which can describe the speed of signal propagation in a heterogeneous medium. We also perform a numerical experiment and discuss its results. Meanwhile, it is shown that with a small number of circles covering a planification of the cylindrical surface, their radius is significantly less than for a similar rectangle.
About the Authors

Alexander L. Kazakov, Dr. Sci. (Phys.-Math.), Prof., Matrosov Institute for System Dynamics and Control Theory SB RAS, Irkutsk National Research Technical University, Irkutsk, 664003, Russian Federation, kazakov@icc.ru

Anna A. Lempert, Cand. Sci. (Phys.-Math.), Matrosov Institute for System Dynamics and Control Theory SB RAS, Irkutsk, 664003, Russian Federation, lempert@icc.ru

Duc Minh Nguyen, Irkutsk National Research Technical University, Irkutsk, 664074, Russian Federation, nguyenducminh.mt@gmail.com

For citation

Kazakov A. L., Lempert A. A., Nguyen D. M. On Covering of Cylindrical and Conical Surfaces with Equal Balls. The Bulletin of Irkutsk State University. Series Mathematics, 2024, vol. 48, pp. 34–48. https://doi.org/10.26516/1997-7670.2024.48.34

Keywords
covering problem, surface of revolution, equal balls, Voronoi diagram
UDC
514.174.3, 519.711.72
MSC
52C15, 37N40, 05B40
DOI
https://doi.org/10.26516/1997-7670.2024.48.34
References
  1. Bezdek A., Fodor F., Vigh V., Zarnocz T. On the multiplicity of arrangements of congruent zones on the sphere. Metric Geometry, 2017.
  2. Bezdek K., Langi Z. From the separable Tammes problem to extremal distributions of great circles in the unit sphere. Discrete Comput. Geom., 2023.https://doi.org/10.1007/s00454-023-00509-w.
  3. Bleicher M.N., Toth L.F. Circle-packings and circle-coverings on a cylinder. Michigan Mathematical Journal, 1964, vol. 11, no. 4, pp. 337–341.https://doi.org/10.1307/mmj/1028999186.
  4. Dorninger D. Thinnest covering of the Euclidean plane with incongruent circles. Analysis and Geometry in Metric Spaces, 2017, vol. 5, pp. 40–46.https://doi.org/10.1515/agms-2017-0002.
  5. Dumer I. Covering spheres with spheres. Discrete & Computational Geometry, 2007, vol. 38, pp. 665–679.
  6. Feynman R., Leighton R., Sands M. Feynman Lectures on Physics. Vol. 3: Radiation. Waves. Quanta. Moscow, Librocom, 2013.
  7. Fodor F., Vigh V., Zarnocz T. Covering the sphere by equal zones. Acta Math. Hungar., 2016, vol. 149, iss. 2, pp. 478–489.
  8. Fortune S. A sweepline algorithm for Voronoi diagrams. Algorithmica, 1987, vol. 2, pp. 153–174.
  9. Galiev Sh. I. Multiple packings and coverings of the sphere. Discrete Mathematics, 1996, vol. 8, no. 3, pp. 148–160.
  10. Gritskevich O.V., Meshcheryakov N.A., Podyanolsky Yu.V. Formation of an optical image of an arbitrary geometric shape on curved surfaces of revolution. Autometry, 1997, no. 2, pp. 26–33. (in Russian)
  11. Karoly B., Gergely W. Covering the Sphere by Equal Spherical Balls. Discrete and Computational Geometry, 2003, vol. 25, pp. 235–251.
  12. Kazakov A.L., Lempert A.A. An Approach to Optimization in Transport Logistics. Automation and Remote Control, 2011, vol. 72, no. 7, pp. 1398–1404.https://doi.org/10.1134/S0005117911070071.
  13. Kazakov A.L., Lempert A.A., Bukharov D.S. On segmenting logistical zones for servicing continuously developed consumers. Automation and Remote Control, 2013, no. 74, pp. 968–977. https://doi.org/10.1134/S0005117913060076.
  14. Kazakov A.L., Lebedev P.D. Algorithms of construction of the best n-networks in metric spaces. Automation and Remote Control, 2017, no. 78, pp. 1290–1301. https://doi.org/10.1134/S0005117917070104.
  15. Lamarche F., Leroy C. Evaluation of the volume of intersection of a sphere with a cylinder by elliptic integrals. Comput. Phys. Commun., 1990, vol. 59, no. 2, pp. 359–369.
  16. Lebedev P.D., Stoychin K.L. Algorithms for Constructing Optimal Covering of Planar Figures with Disks Sets of Linearly Different Radii. The Bulletin of Irkutsk State University. Series Mathematics, 2023, vol. 46, pp. 35–50. (in Russian)https://doi.org/10.26516/1997-7670.2023.46.35.
  17. Lempert A.A., Kazakov A.L., Le Q.M. On reserve and double covering problems for the sets with non-Euclidean metrics. Yugoslav Journal of Operations Research, 2019, vol. 29, no. 1, pp. 69–79. https://doi.org/10.2298/YJOR171112010L.
  18. Nurmela K.J., Patric R.J.O. Covering a square with up to 30 equal circles. Lab. Technol. Helsinki Univ., 2000, 20p.
  19. Ruff I. The Intersection of a Cone and a Sphere: A Contribution to the Geometry of Satellite Viewing. Journal of Applied Meteorology and Climatology, 1971, vol. 10, no. 3, pp. 607–609.
  20. Saulskiy V.K. Multi satellite systems with linear structure and their application for continuous coverage of the earth. Cosmic Research, 2005, vol. 43, no. 1. pp. 34–51. https://doi.org/10.1007/s10604-005-0017-5.
  21. Takhonov I.I. On some problems of covering the plane with circles. Diskretnyi Analiz i Issledovanie Operatsii, 2014, vol. 21, no. 1, pp. 84–102. (in Russian)
  22. Tarnai T., Zsolt G. Covering a Square by Equal Circles. Elemente der Mathematik, 1995, vol. 50, no. 4, pp. 167–170.
  23. Toth G.F., Toth L.F., Kuperberg W. Miscellaneous Problems About Packing and Covering. Lagerungen, Grundlehren der mathematischen Wissenschaften, 2023, vol. 360, pp. 313–336. https://doi.org/10.1007/978-3-031-21800-2_16.
  24. Toth L.F. Arrangements in the Plane, on the Sphere, and in Space. Moscow, Fizmatlit Publ., 1958, 364 p. (in Russian)
  25. Vu D.T., Phung T.B., Lempert A.A., Nguyen D.M. On the problem of the densest packing of spherical segments into a sphere. Management and Administrative Professional Review, 2023, vol. 14, no. 11, pp. 19307–19323.https://doi.org/10.7769/gesec.v14i11.3021.

Full text (english)