On covering of cylindrical and conical surfaces with equal balls

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