The paper focuses on the problem of constructing the thinnest covering for surfaces of revolution by equal balls whose radii are unknown in advance. A heuristic algorithm based on the joint applying the optical-geometric approach and the geodesic Voronoi diagram is proposed. Calculations for some surfaces of revolution, including a sphere, are carried out
covering problem, surface of revolution, equal balls, Voronoi diagram
Построение минимальных (тончайших) покрытий и максимальных (плотнейших) упаковок относится к классическим формулировкам вычислительной геометрии [1]. Такие проблемы изучаются уже на протяжении десятилетий, но до сих пор остаются актуальными [2,3]. Преимущественно рассматриваются покрытия плоских фигур конгруэнтными кругами в различных постановках [4-7]. Задача оптимального покрытия криволинейной поверхности заданным числом равных шаров изучена гораздо меньше. Наиболее очевидным приложением является размещение однотипных беспроводных датчиков и проектирование глобальных навигационных и коммуникационных систем. Во всех случаях покрываемая поверхность является поверхностью вращения. Другим применением является перенос изображения с криволинейной поверхности на плоскость для лазерной размерной обработки поверхностей вращения через плоскую маску [8].
Отметим, что во всех этих прикладных задачах может возникать искажение сигнала, приводящее к нарушению сферической формы зоны действия датчика или передатчика. Как правило, это свойство не учитывается. В данной работе предлагается использовать специальную неевклидову метрику для учета таких эффектов. Она отражает свойства окружающей среды, заменяя физическое расстояние временем, необходимым для его прохождения [9].
Математически, рассматриваемая задача покрытия поверхности 
имеет вид
Здесь 
– число покрывающих шаров с центрами 
радиусом 
. Функция 
задает расстояние между двумя точками и определяется из решения задачи:
Если непрерывная функция 
есть мгновенная скорость движения, то – минимальное время перемещения между точками 
.
Для решения данной задачи предложен эвристический алгоритм, основанный на совместном применении оптико-геометрического подхода [9] и геодезической диаграммы Вороного, позволяющий находить локально-оптимальные решения как для евклидова так и для неевклидова расстояния. Предложена глобализирующая процедура на основе метода мультистарта.
Проведен вычислительный эксперимент, в ходе которого решались серии задач покрытия сферы, цилиндра и тора. В случаях, когда поверхности допускают развертывание, дополнительно проводилось покрытие разверток. На рисунке 1 представлены покрытия единичной сферы 20 кругами (слева) и 100 кругами (справа) и соответствующие им сферические диаграммы Вороного.
Рис. 1. Покрытие единичной сферы равными шарами.
Проведено сравнение результатов расчетов с известными, показавшее, что традиционные геометрические методы являются более быстрыми, а предложенный алгоритм дает более точные результаты.
1. Tot L.F. Raspolozheniya na ploskosti, na sfere i v prostranstve. M.: Fizmatlit, 1958. 364 c.
2. Bezdek K., Langi Z. From the separable Tammes problem to extremal distri-butions of great circles in the unit sphere // Discrete Comput. Geom. 2023. https://doi.org/10.1007/s00454-023-00509-w.
3. 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.
4. Tahonov I.I. O nekotoryh zadachah pokrytiya ploskosti krugami // Diskretnyy analiz i issledovanie operaciy. 2014. Vol. 21, № 1. P. 84-102.
5. Dorninger D. Thinnest covering of the Euclidean plane with incongruent cir-cles // Analysis and Geometry in Metric Spaces. 2017. Vol. 5. P. 40–46.
6. Lebedev P.D., Stoychin K.L. Algoritmy postroeniya optimal'nogo pokrytiya ploskih figur naborami krugov lineyno razlichayuschihsya radiusov // Izvestiya Irkutskogo gosudarstvennogo universiteta. Seriya Matematika. 2023. T. 46. C. 35-50.
7. Lempert A. A., Kazakov A. L., Le Q. M. On reserve and double covering prob-lems for the sets with non-Euclidean metrics // Yugoslav Journal of Operations Research. 2019. Vol. 29, № 1. P. 69-79.
8. Grickevich O.V., Mescheryakov N.A., Pod'yanol'skiy Yu.V. Formirovanie opticheskogo izobrazheniya proizvol'noy geometricheskoy formy na krivo-lineynyh poverhnostyah vrascheniya // Avtometriya. 1997. № 2. S. 26-33.
9. Kazakov A. L., Lempert A. A. Ob odnom podhode k resheniyu zadach optimizacii, voznikayuschih v transportnoy logistike // Avtomatika i telemehani-ka. 2011. T. 72, № 7. S. 50-57.
