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

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

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

МАТЕМАТИКА



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).

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

МАТЕМАТИКА                                                         2013. Вып.4

§ 1. Чебышевский центр множества и его обобщение

   Введем основные определения.
  Определение 1. Хаусдорфовым отклонением [17] компактного множества A с R² от компактного множества B с R² называется число

h(A, B) = max min Ila — bll.
v a    aeA beB

Здесь норма вектора a = (ai, a₂) понимается в евклидовой метрике ||a|| = ||(ai, a₂)|| = \Za+ + 0%, расстояние между точками a и b считается равным ||a — b||.

  Определение 2. Чебышевским центром [10,11] компактного множества M с R² называется такая точка c(M), что
h(M, {c(M)}) = inf h(M, {x}).                  (1.1)
xeR²

Для любого компактного множества он существует и является единственным [12].

  Определение 3. Чебышевским радиусом r(M) компактног о множества M с R² называется величина (1.1).

   Понятия чебышевского центра и радиуса широко используются для оценки различных фигур, особенно при построении схем и карт, когда имеющие ненулевые размеры объекты заменяются точками. Различные варианты отыскания c(M) и r(M) приведены в [6]. Чебышевский центр множества M всегда принадлежит его выпуклой оболочке co M [12].

  Определение 4. На плоскости n-сетью называется непустое множество, состоящее не более чем из n точек в R².


   Естественно ввести для n-сетей некоторое обобщение понятия чебышевского центра. Обозначим через Sₙ множество всех n-сетей пространства R².


  Определение 5. Сеть S* называется наилучшей n-сетью компактного множества M с R²,

если выполняется

h(M, S*) = min h(M, S). seRn


(1-2)

   Сформулируем задачу о наилучшем покрытии множества.

   Задана 1. Рассматриваются ограниченные замкнутые множества M с R² и наборы кругов O(s1, r), O(s₂, r),..., O(sₙ, r) равного радиуса r > 0 c центрам и в точках s1, s₂, ..., sₙ. Назовем r
M C J O(si,r).
i=1,n

M.

nS               M
Ее точки являются центрами кругов наилучшего набора. Радиус кругов равен r = h(M, S). Наилучшая сеть для любого ограниченного множества существует, но не всегда единственна (подробнее см. [10,11]). Далее будем обозначать объединение кругов радиуса r с центрами в точках n-сети S как E(S, r).