Алгоритмы оптимального покрытия множеств на плоскости $\mathbb{R}^2$

 pdf (294K)

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

Ключевые слова: покрытие кругами, наилучшая чебышёвская сеть, чебышёвский центр, зона Дирихле, характерные точки, замкнутая кривая
Цитата: Вестник Удмуртского университета. Математика. Механика. Компьютерные науки, 2016, т. 26, вып. 2, с. 258-270
DOI: 10.20537/vm160212

Algorithms of optimal set covering on the planar $\mathbb{R}^2$

The problem of optimal covering of planar convex sets with a union of a given number $n$ of equal disks is studied. Criterion of optimality is a minimization of disks' radius, which gives an opportunity to reduce the optimization problem to a construction of the best Chebyshev $n$-net of a convex set. Numerical methods based on dividing the set into Dirichlet zones and finding characteristic points are suggested and proved in the present paper. One of the main elements of the methods is a Chebyshev center calculation for a compact convex set. Stochastic algorithms for generating an initial position of the $n$-net points are presented. Modeling of some examples is computed and visualization of the constructed covering is realized.

Keywords: disk covering, best Chebyshev net, Chebyshev center, Dirichlet zone, characteristic points, closed curve
Citation in English: Bulletin of Udmurt University. Mathematics, Mechanics, Computer Science, 2016, vol. 26, issue 2, pp. 258-270

Журнал индексируется в Web of Science (Emerging Sources Citation Index)

Журнал индексируется в Scopus

Журнал входит в базы данных zbMATH, MathSciNet

Журнал включен в базу данных Russian Science Citation Index (RSCI) на платформе Web of Science

Журнал включен в перечень ВАК.

Электронная версия журнала на Общероссийском математическом портале Math-Net.Ru.

Журнал включен в Crossref