Все выпуски

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

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.