рус eng
«ИЗВЕСТИЯ ИРКУТСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА». СЕРИЯ «МАТЕМАТИКА»
«IZVESTIYA IRKUTSKOGO GOSUDARSTVENNOGO UNIVERSITETA». SERIYA «MATEMATIKA»
«THE BULLETIN OF IRKUTSK STATE UNIVERSITY». SERIES «MATHEMATICS»
ISSN 1997-7670 (Print)
ISSN 2541-8785 (Online)

Список выпусков > Серия «Математика». 2024. Том 48

О покрытии поверхности цилиндра и конуса равными шарами

Автор(ы)
А. Л. Казаков1,2, А. А. Лемперт1, Д. М. Нгуен2

1Институт динамики систем и теории управления им. В. М. Матросова СО РАН, Иркутск, Российская Федерация

2Иркутский национальный исследовательский технический университет, Иркутск, Российская Федерация

Аннотация
Рассматривается задача о покрытии равными шарами боковой поверхности прямого кругового цилиндра или конуса. Требуется, чтобы поверхность лежала в их объединении при минимальном радиусе. Центры шаров должны находиться на покрываемой поверхности. Задача представляет интерес как с точки зрения математики, так и для приложений, поскольку возникает в области безопасности и связи. Разработаны эвристические алгоритмы отыскания искомых покрытий, основанные на геодезических диаграммах Вороного. Построение покрытия является нетривиальной задачей, поскольку линией пересечения цилиндра или конуса со сферой является замкнутая кривая 4-го порядка. Для того чтобы сравнить результаты с известными, предложен метод развертывания криволинейных поверхностей на плоскость. Помимо обычного евклидового расстояния, применяется также специальная неевклидовая метрика, которая может характеризовать скорость распространения сигнала в неоднородной среде. Выполнена серия вычислительных экспериментов, по результатам которых удалось сделать некоторые содержательные выводы.
Об авторах

Казаков Александр Леонидович, д-р физ.-мат. наук, проф., Институт динамики систем и теории управления имени В. М. Матросова СО РАН, Иркутский национальный исследовательский технический университет, 664033, Российская Федерация, Иркутск, kazakov@icc.ru

Лемперт Анна Ананьевна, канд. физ.-мат. наук, Институт динамики систем и теории управления имени В. М. Матросова СО РАН, 664033, Российская Федерация, Иркутск, lempert@icc.ru

Нгуен Дык Минь, Иркутский национальный исследовательский технический университет, 664074, Российская Федерация, Иркутск, nguyenducminh.mt@gmail.com

Ссылка для цитирования
Kazakov A. L., Lempert A. A., Nguyen D. M. On Covering of Cylindrical and Conical Surfaces with Equal Balls // Известия Иркутского государственного университета. Серия Математика. 2024. Т. 48. C. 34–48. https://doi.org/10.26516/1997-7670.2024.48.34
Ключевые слова
задача покрытия, поверхность вращения, равные шары, диаграмма Вороного
УДК
514.174.3, 519.711.72
MSC
52C15, 37N40, 05B40
DOI
https://doi.org/10.26516/1997-7670.2024.48.34
Литература
  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, N 4. P. 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. P. 40–46. https://doi.org/10.1515/agms-2017-0002.
  5. Dumer I. Covering spheres with spheres // Discrete & Computational Geometry. 2007. Vol. 38. P. 665–679.
  6. Фейнман Р., Лейтон Р., Сэндс М. Фейнмановские лекции по физике. Т. 3. Излучение. Волны. Кванты. М. : Либроком, 2013.
  7. Fodor F., Vigh V., Zarnocz T. Covering the sphere by equal zones // Acta Math. Hungar. 2016. Vol. 149, Iss. 2. P. 478–489.
  8. Fortune S. A sweepline algorithm for Voronoi diagrams // Algorithmica. 1987. Vol. 2. P. 153–174.
  9. Галиев Ш. И. Многократные упаковки и покрытия сферы // Дискретная математика. 1996. Т. 8, № 3. С. 148–160.
  10. Грицкевич О. В., Мещеряков Н. А., Подъянольский Ю. В. Формирование оптического изображения произвольной геометрической формы на криволинейных поверхностях вращения // Автометрия. 1997. № 2. С. 26–33.
  11. Karoly B., Gergely W. Covering the Sphere by Equal Spherical Balls // Discrete and Computational Geometry. 2003. Vol. 25. P. 235–251.
  12. Казаков А. Л., Лемперт А. А. Об одном подходе к решению задач оптимизации, возникающих в транспортной логистике // Автоматика и телемеханика. 2011. Т. 72, № 7. С. 50–57. https://doi.org/10.1134/S0005117911070071.
  13. Казаков А. Л., Лемперт А. А., Бухаров Д. С. К вопросу о сегментации логистических зон для обслуживания непрерывно распределенных потребителей // Автоматика и телемеханика. 2013. № 6. С. 87–100. https://doi.org/10.1134/S0005117913060076.
  14. Казаков А. Л., Лебедев П. Д. Алгоритмы построения наилучших n-сетей в метрических пространствах // Автоматика и телемеханика. 2017. № 7. С. 141– 155. 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, N 2. P. 359–369.
  16. Лебедев П. Д., Стойчин К. Л. Алгоритмы построения оптимального покрытия плоских фигур наборами кругов линейно различающихся радиусов // Известия Иркутского государственного университета. Серия Математика. 2023. Т. 46. C. 35–50. 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, N 1. P. 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, N 3. P. 607–609.
  20. Saulskiy V. K. Multisatellite systems with linear structure and their application for continuous coverage of the earth // Cosmic Research. 2005. Vol. 43, N 1. P. 34–51. https://doi.org/10.1007/s10604-005-0017-5.
  21. Тахонов И. И. О некоторых задачах покрытия плоскости кругами // Дискретный анализ и исследование операций. 2014. Т. 21, № 1. P. 84–102.
  22. Tarnai T., Zsolt G. Covering a Square by Equal Circles // Elemente der Mathematik. 1995. Vol. 50, N 4. P. 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. P. 313–336. https://doi.org/10.1007/978-3-031-21800-2_16.
  24. Тот Л. Ф. Расположения на плоскости, на сфере и в пространстве. М. : Физматлит, 1958. 364 c.
  25. On the problem of the densest packing of spherical segments into a sphere / D. T. Vu, T. B. Phung, A. A. Lempert, D. M. Nguyen // Management and Administrative Professional Review. 2023. Vol. 14, N 11. P. 19307–19323. https://doi.org/10.7769/gesec.v14i11.3021.

Полная версия (english)