Алгоритмы построения оптимального покрытия плоских фигур наборами кругов линейно различающихся радиусов

Рассмотрена задача об оптимальном покрытии плоских фигур наборами из фиксированного числа различных кругов. Считается, что каждый круг имеет радиус, равный сумме общего для всех параметра и его индивидуального числа. Основная цель работы — разработать алгоритмы, которые позволяют строить покрытия при минимальном общем параметре. Показано, что задача может быть сведена к минимизации функции нескольких переменных, зависящих от координат центров кругов. Изучены зоны влияния точек, служащих центрами кругов при фиксированном наборе индивидуальных чисел. Предложен итерационный алгоритм решения задачи, использующий понятия чебышевского центра и обобщение зоны Дирихле. Выведены соотношения, аналитически описывающие эти зоны. Доказана теорема об эффективности работы алгоритма. Показаны возможности применения результатов статьи к построению сетей датчиков. Приведен ряд примеров решения задач о построении оптимального покрытия для различных выпуклых многоугольников.