Алгоритмы наилучшей аппроксимации плоских множеств объединениями кругов

 pdf (261K)

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

Ключевые слова: чебышевский центр, наилучшая n-сеть, покрытие кругами
Цитата: Вестник Удмуртского университета. Математика. Механика. Компьютерные науки, 2013, вып. 4, с. 88-99
DOI: 10.20537/vm130409

Algorithms of the best approximations of the flat sets by the union of circles

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.

Keywords: Chebyshev center, the best net, circle cover
Citation in English: Bulletin of Udmurt University. Mathematics, Mechanics, Computer Science, 2013, issue 4, pp. 88-99

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

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

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

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

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

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

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