Все выпуски

Работа посвящена проблеме построения наилучшего аппроксимирующего покрытия ограниченного плоского множества M конечным набором кругов одного радиуса. Проблема считается решенной, если удалось построить наилучшую в смысле хаусдорфовой метрики n-сеть рассматриваемого множества. В работе приведены достаточные условия оптимальности n-сети, предложен алгоритм построения наилучших сетей на основе разбиения M на подмножества и отыскания их чебышевских центров. Эффективность созданного алгоритма показана на примерах множеств с различной геометрией.

Изучается задача об оптимальном покрытии выпуклых множеств на плоскости объединением заданного числа $n$ кругов одинакового радиуса. Критерий оптимальности заключается в минимизации радиуса кругов, что позволяет свести задачу оптимизации к задаче построения наилучшей чебышёвской $n$-сети выпуклого множества. В работе предложены и обоснованы численные методы, базирующиеся на разбиении множества на области Дирихле и отыскании так называемых характерных точек. Одним из ключевых элементов методов является построение чебышёвского центра компактного выпуклого множества. Представлены стохастические алгоритмы генерации начального положения точек $n$-сети. Проведено моделирование ряда примеров и выполнена визуализация построенных покрытий.