УДК 514.174.2
MSC: 05B40, 52C17, 35A18
DOI: 10.21538/0134-4889-2024-30-1-142-155
Исследования А.А. Лемперт выполнены в рамках госзадания Минобрнауки России по проекту “Теоретические основы, методы и высокопроизводительные алгоритмы непрерывной и дискретной оптимизации для поддержки междисциплинарных научных исследований”
(№ гос. регистрации: 121041300065-9).
Рассматривается задача о покрытии заданным числом элементов поверхности трехмерного множества, когда последнее — шар или шаровый сегмент, а элементы покрытия — равные сферические сегменты. Критерием оптимизации является минимизация радиуса данных сегментов. Такая постановка относится к относительно мало изученным случаям классической задачи о покрытии односвязного множества шарами, которая актуальна в связи с приложениями в области информационно-телекоммуникационных технологий и логистики. Особенность данного исследования заключается в том, что помимо традиционного евклидового расстояния между точками рассматривается также специальная метрика, характеризующая меру удаленности точек как время перемещения между ними. Предложен новый эвристический алгоритм, основанный на применении сферического аналога диаграммы Вороного и традиционной для авторов оптико-геометрической аналогии, позволяющий решать задачу покрытия неплоских поверхностей. Поскольку материал для сравнения с метрикой общего вида найти не удалось, был особо рассмотрен случай геодезического расстояния на сфере, для которого разработан алгоритм построения наилучшего покрытия посредством отыскания чебышевских центров зон Дирихле с доказательством теоремы, позволяющей оценить его эффективность. Выполнены иллюстрирующие численные расчеты.
Ключевые слова: оптимальное покрытие, неевклидово расстояние, диаграмма Вороного, оптическо-геометрическая аналогия, чебышевский центр
СПИСОК ЛИТЕРАТУРЫ
1. Кротов В.Ф., Пиявский С.А. Достаточные условия оптимальности в задачах об оптимальных покрытиях // Изв. АН СССР. Техническая кибернетика. 1968. №2. С. 10–17.
2. Toth L.F. Solid circle-packings and circle-coverings // Studia Sci. Math. Hungar. 1968. Vol. 3. P. 401–409.
3. Брусов В.С., Пиявский С.А. Вычислительный алгоритм оптимального покрытия областей плоскости // Журн. вычисл. математики и мат. физики. 1971. Т. 11, №2. С. 304–313.
4. Казаков А.Л., Лемперт А.А. Об одном подходе к решению задач оптимизации, возникающих в транспортной логистике // Автоматика и телемеханика. 2011. Т. 72, № 7. С. 50–57.
5. Можаев Г.В. Задача о непрерывном обзоре поверхности Земли и кинематически правильные спутниковые системы // Космические исследования. 1972. Т. 10, №6. С. 833–840.
6. Пиявский С.А. Об оптимизации сетей // Изв. АН СССР. Техническая кибернетика. 1968. №1. С. 68–80.
7. Зикратовa И.А., Шаго Ф.Н. Гуртов А.В., Иванинская И.И. Оптимизация зоны покрытия сети сотовой связи на основе математического программирования // Науч.-техн. вестн. информ. технологий, механики и оптики. 2015. Т. 15, №2. С. 313–321.
doi: 10.17586/2226-1494-2015-15-2-313-321
8. Казаковцев Л.А., Гудыма М.Н., Ступина А.А., Кириллов Ю.И. Задача выбора оптимального размещения элементов беспроводной сети // Современные проблемы науки и образования. 2013. №3. С. 85–92.
9. Гениатулин К.А., Носов В.И. Применение метода координационных колец при частотно-территориальном планировании системы спутниковой связи с зональным обслуживанием // Вестн. СибГУТИ. 2014. №1. С. 35–45.
10. Бычков И.В., Казаков А.Л., Лемперт А.А. и др. Интеллектная система управления развитием транспортно-логистической инфраструктурой региона // Проблемы управления. 2014. Т. 1. С. 27–35.
11. Казаковцев Л.А., Гудыма М.Н. Постановка задачи оптимального размещения сети датчиков мониторинга загрязнения воздуха и воды // Перспективы развития информационных технологий. 2013. №13. С. 19–24.
12. Heppes A., Melissen H. Covering a rectangle with equal circles // Period. Math. Hungar. 1977. Vol. 34. P. 65–81. doi: 10.1023/A:1004224507766
13. Melissen J.B.M., Schuur P.C. Covering a rectangle with six and seven circles // Discret. Appl. Math. 2000. Vol. 99. P. 149–156. doi: 10.1016/S0166-218X(99)00130-4
14. Nurmela K.J. Conjecturally optimal coverings of an equilateral triangle with up to 36 equal circles // Experimental Math. 2000. Vol. 9, no. 2. P. 241–250. doi: 10.1080/10586458.2000.10504649
15. Nurmela K.J., Ostergard P.R.J. Covering a square with up to 30 equal circles // Helsinki University of Technology — Research Reports. 2000. Vol. 99. P. 149–156.
16. Conway J.H., Sloane N.J.A. Sphere Packing. Lattices and Groups. NY: Springer, 1999. 706 p. doi: 10.1007/978-1-4757-6568-7
17. Тахонов И.И. О некоторых задачах покрытия плоскости кругами // Дискрет. анализ и исследование операций. 2014. Т. 21. Вып. 1. C. 84–102.
18. Dorninger D. Thinnest covering of the Euclidean plane with incongruent circles // Analysis and Geometry in Metric Spaces. 2017. Vol. 5. P. 40–46. doi: 10.1515/agms-2017-0002
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. 2018. Vol. 77. P. 77–82. doi: 10.1007/s10998-018-0241-4 .
22. Bondarenko A., Prymak A., Radchenko D. Spherical coverings and X-raying convex bodies of constant width // Canad. Math. Bull. 2021. Vol. 65. P. 1–7.
23. Стоян Ю.Г., Пацук В.Н. Метод покрытия выпуклого многогранного множества минимальным количеством одинаковых шаров // Reports of the National Acad. Sci. Ukraine. 2009. Vol. 5. Р. 41–45.
24. Verger-Gaugry J.L. Covering a ball with smaller equal balls in $R^n$ // Discrete & Computational Geometry. 2005. Vol. 33, no. 1. P. 143–155. doi: 10.1007/s00454-004-2916-2
25. Dumer I. Covering spheres with spheres // Discrete & Computational Geometry. 2007. Vol. 38, no. 4. P. 665–679. doi: 10.1007/s00454-007-9000-7
26. Bezdek A., Fodor F., Vigh V., Zarnocz T. On the multiplicity of arrangements of congruent zones on the sphere [e-resource]. 2023. 11 p. URL: https://arxiv.org/abs/1705.02172 .
27. Галиев Ш.И. Многократные упаковки и покрытия сферы // Дискрет. математика. 1996. Т. 8. №3. С. 148–160.
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) / eds. Yu. I. Shokin, H. Milosevic, D. V. Esipov. Ser. CEUR Workshop Proceedings. 2017. Vol. 1839. P. 334–343. URL: https://ceur-ws.org/Vol-1839/MIT2016-p30.pdf
29. Казаков А.Л., Лебедев П.Д. Алгоритмы построения наилучших n-сетей в метрических пространствах // Автоматика и телемеханика. 2017. №7. С. 141–155.
30. Казаков А.Л., Лемперт А.А., Бухаров Д.С. К вопросу о сегментации логистических зон для обслуживания непрерывно распределенных потребителей // Автоматика и телемеханика. 2013. №6. С. 87–100.
31. Фейнман Р., Лейтон Р., Сэндс М. Фейнмановские лекции по физике. Том 3: Излучение. Волны. Кванты. М.: Либроком, 2013. 243 с.
32. Fortune S. A sweepline algorithm for Voronoi diagrams // Algorithmica. 1987. Vol. 2. P. 153–174. doi: 10.1007/BF01840357
33. Shkaberina G., Verenev L., Tovbis E., Rezova N., Kazakovtsev L. Clustering algorithm with a greedy agglomerative heuristic and special distance measures // Algorithms. 2022. Vol. 15, no. 6. P. 191. doi: 10.3390/a15060191
34. Лебедев П.Д. Программа вычисления оптимального покрытия полусферы набором сферических сегментов. Программа для ЭВМ. Регистр. номер 2015661543. Дата регистрации 29.10.2015.
35. Арестов В.В., Бабенко А.Г. О схеме Дельсарта оценки контактных чисел // Тр. МИАН. 1997. Т. 219. С. 44–73.
36. Степанов Н.Н. Сферическая тригонометрия. Л.; М.: ОГИЗ, 1948. 154 с.
37. Ушаков В.Н., Лахтин А.С., Лебедев П.Д. Оптимизация хаусдорфора расстояния между множествами в евклидовом пространстве // Тр. Ин-та математики и механики УрО РАН. 2014. Т. 20, № 3. С. 291–308.
Поступила 30.10.2023
После доработки 29.12.2023
Принята к публикации 9.01.2024
Лемперт Анна Ананьевна
канд. физ.-мат. наук, ведущий науч. сотрудник
Институт динамики систем и теории управления имени В.М. Матросова СО РАН
г. Иркутск
e-mail: lempert@icc.ru
Лебедев Павел Дмитриевич
канд. физ.-мат. наук, старший науч. сотрудник
Институт математики и механики им. Н.Н. Красовского УрО РАН;
Уральский федеральный университет
г. Екатеринбург
e-mail: pleb@yandex.ru
Нгуен Дык Минь
аспирант
Иркутский национальный исследовательский технический университет, г. Иркутск
e-mail: nguyenducminh.mt@gmail.com
Ссылка на статью: А.А. Лемперт, П.Д. Лебедев, Д.М. Нгуен. О задаче покрытия сферических фигур равными сферическими сегментами // Тр. Ин-та математики и механики УрО РАН. 2024. Т. 30, № 1. С. 142-155
English
A.A. Lempert, P.D. Lebedev, D.M. Nguyen. On the problem of covering spherical figures with equal spherical caps
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.
Keywords: optimal covering, non-Euclidean distance, Voronoi diagram, optical-geometric analogy, Chebyshev center
Received October 30, 2023
Revised December 29, 2023
Accepted January 9, 2024
Funding Agency: The first author was supported by the Ministry of Education and Science of the Russian Federation within the project “Theoretical foundations, methods, and high-performance algorithms for continuous and discrete optimization to support interdisciplinary scientific research” (state registration no. 121041300065-9).
Anna Ananievna Lempert, Cand. Sci. (Phys.-Math.), Matrosov Institute for System Dynamics and Control Theory of the Siberian Branch of the Russian Academy of Sciences, Irkutsk, 664033 Russia, e-mail: lempert@icc.ru
Duc Minh Nguyen, doctoral student, Irkutsk National Research Technical University, Irkutsk, 664033 Russia, e-mail: nguyenducminh.mt@gmail.com
Pavel Dmitrievich Lebedev, Cand. Sci. (Phys.-Math.), Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620108 Russia, Ural Federal University, Yekaterinburg, 620000 Russia, e-mail: pleb@yandex.ru
Cite this article as: A.A. Lempert, P.D. Lebedev, D.M. Nguyen. On the problem of covering spherical figures with equal spherical caps. Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2024, vol. 30, no. 1, pp. 142–155.
[References -> on the "English" button bottom right]
