On covering of cylindrical and conical surfaces with equal balls

Alexander L. Kazakov ; Anna A. Lempert ; Duc Minh Nguyen

The Bulletin of Irkutsk State University. Series Mathematics, Tome 48 (2024), pp. 34-48

Résumé

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.

Détail

Keywords: covering problem, surface of revolution, equal balls, Voronoi diagram.

Bibliographie

[1] Bezdek A., Fodor F., Vigh V., Zarnocz T., “On the multiplicity of arrangements of congruent zones on the sphere”, Metric Geometry, 2017 | Zbl

[2] Bezdek K., Langi Z., “From the separable Tammes problem to extremal distributions of great circles in the unit sphere”, Discrete Comput. Geom., 2023 | DOI | MR

[3] Bleicher M. N., Toth L. F., “Circle-packings and circle-coverings on a cylinder”, Michigan Mathematical Journal, 11:4 (1964), 337–341 | DOI | MR | Zbl

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

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

[6] Feynman R., Leighton R., Sands M., Feynman Lectures on Physics, v. 3, Radiation. Waves. Quanta, Librocom, M., 2013 | MR

[7] Fodor F., Vigh V., Zarnocz T., “Covering the sphere by equal zones”, Acta Math. Hungar, 149:2 (2016), 478–489 | DOI | MR | Zbl

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

[9] Galiev Sh. I., “Multiple packings and coverings of the sphere”, Discrete Mathematics, 8:3 (1996), 148–160 | DOI | Zbl

[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, 26–33 (in Russian)

[11] Karoly B., Gergely W., “Covering the Sphere by Equal Spherical Balls”, Discrete and Computational Geometry, 25 (2003), 235–251 | DOI | MR | Zbl

[12] Kazakov A.L., Lempert A.A., “An Approach to Optimization in Transport Logistics”, Automation and Remote Control, 72:7 (2011), 1398–1404 | DOI | MR | Zbl

[13] Kazakov A.L., Lempert A.A., Bukharov D.S., “On segmenting logistical zones for servicing continuously developed consumers”, Automation and Remote Control, 74:6 (2013), 968–977 | DOI | MR | Zbl

[14] Kazakov A.L., Lebedev P.D., “Algorithms of construction of the best n-networks in metric spaces”, Automation and Remote Control, 78:7 (2017), 1290–1301 | DOI | MR | Zbl

[15] Lamarche F., Leroy C., “Evaluation of the volume of intersection of a sphere with a cylinder by elliptic integrals”, Comput. Phys. Commun., 59:2 (1990), 359–369 | DOI | MR

[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, 46 (2023), 35–50 | DOI | Zbl

[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, 29:1 (2019), 69–79 | DOI | MR | Zbl

[18] Nurmela K. J., Patric R. J. O., Covering a square with up to 30 equal circles, Lab. Technol. Helsinki Univ, 2000, 20 pp.

[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, 10:3 (1971), 607–609 | 2.0.CO;2 class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI

[20] Saulskiy V. K., “Multisatellite systems with linear structure and their application for continuous coverage of the earth”, Cosmic Research, 43:1 (2005), 34–51 | DOI

[21] Takhonov I.I., “On some problems of covering the plane with circles”, Diskretnyi Analiz i Issledovanie Operatsii, 21:1 (2014), 84–102 (in Russian) | MR | Zbl

[22] Tarnai T., Zsolt G., “Covering a Square by Equal Circles”, Elemente der Mathematik, 50:4 (1995), 167–170 | MR | Zbl

[23] Toth. G. F., Toth. L. F., Kuperberg W., “Miscellaneous Problems About Packing and Covering”, Lagerungen, Grundlehren der mathematischen Wissenschaften, 360, 2023, 313–336 | DOI | MR

[24] Toth L.F., Arrangements in the Plane, on the Sphere, and in Space, Fizmatlit Publ, M., 1958, 364 pp. (in Russian)

[25] D. T. Vu, T. B. Phung, A. A. Lempert, D. M. Nguyen, “On the problem of the densest packing of spherical segments into a sphere”, Management and Administrative Professional Review, 14:11 (2023), 19307–19323 | DOI