Все выпуски

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

The problem of minimizing the Hausdorff distance between two convex polygons is studied. The first polygon is supposed to be able to make any flat motions including parallel transportation and rotation with the center at any point. The second polygon is supposed to be fixed. Iterative algorithms of step-by-step displacements and rotations of the polygon which provide a decrease in the Hausdorff distance between the moving polygon and the fixed polygon are developed and realized in software programs. Some theorems of correctness of the algorithms are proved for a wide range of cases. Geometrical properties of the Chebyshev center of a compact set and differential properties of the function of Euclidean distance to a convex set are used. The possibility of a multiple launch is provided for in the implementation of the software complex for the purpose of identifying the best found position of the polygon. Modeling for several examples is performed.

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

The article is devoted to the problem of constructing an optimal approximating circle-cover for the bounded flat set by the finite number of circles with equal radius. The problem is solved if the best n-net in meaning of Hausdorff metric is constructed for the considered set. Sufficient conditions of optimality of the n-nets are given. The best net-construction algorithm based on dividing of the set M into subsets and finding their Chebyshev centers is realized. This algorithm is proved to be efficient with the examples of sets with different geometry.

Изучается задача об оптимальном покрытии выпуклых множеств на плоскости объединением заданного числа $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.