Рассмотрена задача построения тончайшего покрытия поверхностей вращения шарами, радиусы которых равны и заранее неизвестны. Предложен эвристический алгоритм ее решения, основанный на совместном применении оптико-геометрического подхода и геодезической диаграммы Вороного. Выполнены расчеты для некоторых поверхностей вращения, включая сферу
задача покрытия, поверхность вращения, равные шары, диаграмма Вороного
Построение минимальных (тончайших) покрытий и максимальных (плотнейших) упаковок относится к классическим формулировкам вычислительной геометрии [1]. Такие проблемы изучаются уже на протяжении десятилетий, но до сих пор остаются актуальными [2,3]. Преимущественно рассматриваются покрытия плоских фигур конгруэнтными кругами в различных постановках [4-7]. Задача оптимального покрытия криволинейной поверхности заданным числом равных шаров изучена гораздо меньше. Наиболее очевидным приложением является размещение однотипных беспроводных датчиков и проектирование глобальных навигационных и коммуникационных систем. Во всех случаях покрываемая поверхность является поверхностью вращения. Другим применением является перенос изображения с криволинейной поверхности на плоскость для лазерной размерной обработки поверхностей вращения через плоскую маску [8].
Отметим, что во всех этих прикладных задачах может возникать искажение сигнала, приводящее к нарушению сферической формы зоны действия датчика или передатчика. Как правило, это свойство не учитывается. В данной работе предлагается использовать специальную неевклидову метрику для учета таких эффектов. Она отражает свойства окружающей среды, заменяя физическое расстояние временем, необходимым для его прохождения [9].
Математически, рассматриваемая задача покрытия поверхности 
имеет вид
Здесь 
– число покрывающих шаров с центрами 
радиусом 
. Функция 
задает расстояние между двумя точками и определяется из решения задачи:
Если непрерывная функция 
есть мгновенная скорость движения, то – минимальное время перемещения между точками 
.
Для решения данной задачи предложен эвристический алгоритм, основанный на совместном применении оптико-геометрического подхода [9] и геодезической диаграммы Вороного, позволяющий находить локально-оптимальные решения как для евклидова так и для неевклидова расстояния. Предложена глобализирующая процедура на основе метода мультистарта.
Проведен вычислительный эксперимент, в ходе которого решались серии задач покрытия сферы, цилиндра и тора. В случаях, когда поверхности допускают развертывание, дополнительно проводилось покрытие разверток. На рисунке 1 представлены покрытия единичной сферы 20 кругами (слева) и 100 кругами (справа) и соответствующие им сферические диаграммы Вороного.
Рис. 1. Покрытие единичной сферы равными шарами.
Проведено сравнение результатов расчетов с известными, показавшее, что традиционные геометрические методы являются более быстрыми, а предложенный алгоритм дает более точные результаты.
1. Тот Л.Ф. Расположения на плоскости, на сфере и в пространстве. М.: Физматлит, 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. Тахонов И.И. О некоторых задачах покрытия плоскости кругами // Дискретный анализ и исследование операций. 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. Лебедев П.Д., Стойчин К.Л. Алгоритмы построения оптимального покрытия плоских фигур наборами кругов линейно различающихся радиусов // Известия Иркутского государственного университета. Серия Математика. 2023. Т. 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. Грицкевич О.В., Мещеряков Н.А., Подъянольский Ю.В. Формирование оптического изображения произвольной геометрической формы на криво-линейных поверхностях вращения // Автометрия. 1997. № 2. С. 26-33.
9. Казаков А. Л., Лемперт А. А. Об одном подходе к решению задач оптимизации, возникающих в транспортной логистике // Автоматика и телемехани-ка. 2011. Т. 72, № 7. С. 50-57.
