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


ВЕСТНИК УДМУРТСКОГО УНИВЕРСИТЕТА

МАТЕМАТИКА. МЕХАНИКА. КОМПЬЮТЕРНЫЕ НАУКИ

МАТЕМАТИКА



2013. Вып.4

УДК 514.174.3


© П. Д. Лебедев, А. А. Успенский, В. Н. Ушаков
АЛГОРИТМЫ НАИЛУЧШЕЙ АППРОКСИМАЦИИ ПЛОСКИХ МНОЖЕСТВ ОБЪЕДИНЕНИЯМИ КРУГОВ¹

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

Ключевые слова: чебышевский центр, наилучшая n-сеть, покрытие кругами.



Введение

   Задача построения аппроксимации множества актуальна, а алгоритмы построения аппроксимирующих множеств с заданными свойствами находят много приложений. Примером отрасли знания, в которой активно применяются алгоритмы аппроксимации множеств, является теория позиционного управления [1]. В динамических задачах управления разрешающие множества (стабильные мосты, интегральные воронки, множества достижимости) имеют, как правило, сложную геометрию и нерегулярную с точки зрения гладкости границу. Точное построение разрешающих множеств представляет трудно разрешимую задачу, которая на практике обходится подменой разрешающего множества другим множеством, чаще всего его аппроксимацией. Естественно, что замена разрешающего множества другим множеством должна быть корректной. В задачах управления такая подмена множеств считается корректной, если вновь построенное множество имеет приемлемый (малый) дефект стабильности [2,3]. Если при этом сконструированное множество имеет достаточно гладкую границу, то это служит дополнительным побудительным мотивом осуществления такой замены [4,5], поскольку гладкость границы множества облегчает построение управляющих воздействий. В связи с этим одним из перспективных направлений исследований для нужд теории управления является разработка алгоритмов аппроксимации ограниченных множеств конечными наборами шаров одинакового радиуса [6,7]. Похожие по постановке задачи об аппроксимации множеств эллипсами рассматривались А. Б. Куржанским [8] и его сотрудниками [9].
   Основным элементом для построения покрытия множеств шарами в пространствах конечной размерности является так называемая наилучшая n-сеть, обобщающая понятие чебышевского центра. Условия существования и единственности таких сетей были изучены А. Л. Гар-кави [10-13] и Е.Н. Сосовым [14-16].
n
наилучшей. Предложены аналитические и численные методы построения наборов 5 из n кругов, аппроксимирующих наилучшим образом плоские множества. Критерием оптимальности выбран минимум радиуса кругов (при фиксированном их количестве). В этом случае точки наилучшей n-сети являются центра ми кругов из набора 5. Приведены примеры численного моделирования.
   Работа выполнена при поддержке грантов РФФИ № 11-01-00427-а, Программы президиума РАН «Математические модели и алгоритмы в управляемых системах с нелинейной динамикой» при финансовой поддержке УрО РАН (проект № 12-П-1-1012) и Программы президиума РАН «Динамические системы и теория управления» при финансовой поддержке Уральского Отделения РАН (проект № 12-П-1-1002).