ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2011, том 51, № 6, с. 1018-1031
УДК 519.626
ОБ ОПТИМАЛЬНОМ ПОРЯДКЕ РОСТА ЧИСЛА ВЕРШИН И ГИПЕРГРАНЕЙ В КЛАССЕ ХАУСДОРФОВЫХ МЕТОДОВ ПОЛИЭДРАЛЬНОЙ АППРОКСИМАЦИИ ВЫПУКЛЫХ ТЕЛ1)
© 2011 г. Р. В. Ефремов*, Г. К. Каменев**
(*28933 Mostoles, Madrid (España), Universidad Rey Juan Carlos;
**119333 Москва, ул. Вавилова, 40, ВЦ РАН) e-mail: gkk@ccas.ru Поступила в редакцию 25.08.2010 г.
Переработанный вариант 20.10.2010 г.
Рассматриваются вопросы внутренней полиэдральной аппроксимации выпуклых компактных тел с дважды непрерывно дифференцируемыми границами и положительными главными кривизнами. Исследуется рост числа гиперграней в классе хаусдорфовых адаптивных методов внутренней полиэдральной аппроксимации, асимптотически оптимальных по порядку роста числа вершин аппроксимирующих многогранников. Показано, что порядок роста числа гиперграней наряду с порядком роста числа вершин является оптимальным. Получены явные выражения для констант в соответствующих оценках. Библ. 33. Фиг. 2.
Ключевые слова: гладкое выпуклое тело, аппроксимация многогранником, метод аппроксимации, оптимальные методы, скорость сходимости аппроксимации, гранная структура.
1. Аппроксимация многогранниками является традиционным средством теории выпуклых множеств. Первые аппроксимационные теоремы восходят к Минковскому [1]. Эти утверждения широко использовались (см., например, [2]) для получения результатов, связанных с геометрией выпуклых поверхностей. Задача аппроксимации с точки зрения сложности аппроксимирующих многогранников в виде числа элементов гранной структуры, таких как вершины или гиперграни, также была исследована. Были получены асимптотические оценки минимального числа вершин или гиперграней, необходимых для получения заданной точности аппроксимации (см., например, обзоры в [3], [4]). Вместе с тем о полной мощности гранной структуры аппроксимирующих многогранников известно значительно меньше. Так, в [5] получены для размерности пространства большей или равной четырем оценки зависимости точности аппроксимации от ограничения на максимальное число граней произвольной размерности. Оценки получены для гладких тел с точностью до неопределенных констант. В [6] в трехмерном случае получена асимптотика для числа ребер (1-мерных граней). Из формулы Эйлера следуют в этом случае оценки, аналогичные полученным в [5].
Наряду с задачей оценки минимального числа граней или вершин, необходимых для достижения заданной точности, стоит практически важная задача разработки оптимальных методов полиэдральной аппроксимации выпуклых компактных тел. Такая задача возникает во многих приложениях: в теории оптимального управления (см. [7]), кодировании изображении (см. [8]), математическом моделировании (см. [9]). Важное практическое значение вычислительные алгоритмы полиэдральной аппроксимации имеют в задачах многокритериальной оптимизации и принятия решений (см. [10], [11]). В рамках этих исследований был предложен в [12] и разработан в [10], [11] адаптивный метод "уточнения оценок", который показал себя практически пригодным для аппроксимации выпуклых обобщенных множеств достижимости большой размерности. В качестве обобщения и исследования этого метода было начато развитие теории оптимальных адаптивных методов полиэдральной аппроксимации: в [13], [14] был предложен, теоретически (см. [15]—[18]) и экспериментально (см. [19]) исследован и нашел практическое
1) Работа выполнена при частичной финансовой поддержке РФФИ (коды проектов 09-01-00599 и 10-01-00199), ПФИ Президиума РАН П-14 и ПФИ ОМН РАН № 3, Министерства Науки и Инноваций Испании (TIN2008-06796-C04-01/TSI), Департамента Образования автономной области Мадрид (S2009/esp-1594).
применение (см. [10], [11]) класс хаусдорфовых (или H-) методов полиэдральной аппроксимации (см. обзор результатов в [10], [11], [20]).
В [13]—[15] было показано, что при аппроксимации гладких тел хаусдорфовы методы восполнения являются оптимальными по порядку числа вершин аппроксимирующих многогранников. В настоящей работе исследуется рост числа гиперграней в этом классе методов восполнения. Показано, что порядок роста числа гиперграней тот же, что и порядок роста числа вершин, и является оптимальным. Исследования проводятся для случая, когда аппроксимируемые тела имеют дважды непрерывно дифференцируемые границы и положительные главные кривизны. Получены явные выражения для констант в соответствующих оценках.
2. Рассмотрим евклидово пространство Е со скалярным произведением (■, ■) , расстоянием р(-, ■) и нормой |М1 . Обозначим через % класс выпуклых компактных множеств с непустой внутренностью, т.е. выпуклых компактных тел. Через дС обозначим границу тела С, через int С — мно-
2
жество его внутренних точек, через ст(С) — его поверхностный объем. Обозначим через % + класс выпуклых компактных тел с дважды непрерывно дифференцируемой границей и положительными главными кривизнами. Через RdC и гдС обозначим максимальный и минимальный радиусы
кривизны дС, С е %+, соответственно. Пусть ¥, ¥ с %, — класс выпуклых телесных многогранников (выпуклых оболочек конечного множества точек, не лежащих в одной гиперплоскости). Для P е ¥ через Mt(P) обозначим множество его вершин (граней нулевой размерности), а через m'(P) — число его вершин, через Mf(P) обозначим множество векторов единичных внешних нормалей к его гиперграням (граням размерности (d — 1)), а через mf(P) — число его гиперграней. Обозначим через С(п, к) число сочетаний из n по к, через card T — мощность множества T, через
|_ ■ J — ближайшее число снизу. Обозначим через Bd(r, z) шар в Е радиуса r с центром в z, а через Bd(r) — шар радиуса r с центром в начале координат, единичный шар обозначим через Bd, и пусть Sd-1 := dBd. Обозначим через cl операцию замыкания и через aff и cony — операции взятия аффинной и выпуклой оболочек соответственно. Через proj(x, X) обозначим проекцию точки х на множество X. Конусом видимости K(p, С) тела С из точки p £ С назовем минимальный конус с
вершиной вp, содержащий С. Для Се % и u е Е \{0} введем обозначения опорной функции
g(u, С): = max{(u, х): х е С} и опорной гиперплоскости l(u, С) := {х е Е : (u , х) = g(u, С)}.
Для Се % введем класс ¥ (С) внутренних многогранников, вершины которых принадлежат дС (вписанных многогранников). Определим также классы
¥(C) := {P е ¥(C): m (P) < m},
®'lm](C) := {P е ¥ (C): mf(P)< m}.
Рассмотрим традиционную (см. [3], [4]) для рассматриваемой задачи метрику Хаусдорфа
S(Ci, C2) := max{sup{p(x, C2): x е Cx}, sup{p(x, Cx): x е C2}}.
Обозначим также величины минимально достижимого отклонения в заданных классах многогранников аппроксимации:
5(C, ¥m) := inf{5(C, P): P е (C)},
5(C, ¥m]) := inf{S(C, P): P е ^ (C)}. Известна следующая оценка на эти величины (см. [21], [22]), С е %:
S( C, ¥m ),5( C, ¥m] )< . (1)
m
Здесь и далее через сопб^, Ь. обозначаются положительные константы, зависящие только от параметров а, Ь, .... При аппроксимации достаточно гладких тел известна точная асимптотика
(см. [23]), С е % + :
\2Kd-1)
2/(d - 1) 1
Иш 5(С,&'я)я2/(d-1) = 1 ^ Гкс(х)1/2dv(x) я 2 ^ - 1 ^
Иш 5( с, ^[я]) я2/( d -1) = 1 Г кс (х)1/2 do(x)
я ^ю 21 %d -1
(2)
дС
2/(d -1)
, (3)
где есть плотность покрытия пространства Е' шарами фиксированного радиуса (см. [24]), яё := := яё/2/Г((ё/2) + 1) — объем единичного шара, кС(х) — кривизна Гаусса—Кронекера (произведение главных кривизн) в точке х е дС и ст(х) — элемент поверхностного объема в точке х. Заметим, что
точно известны только величины = 1 и $2 = 2я/л/27 . Оценки для остальных величин найдены, например, в [25]. История получения оценок (2), (3) рассмотрена в обзорах [3], [4]. Отметим, что члены следующего порядка малости по т в асимптотике вида (2), (3) рассмотрены, например, в [26].
Пусть теперь
я}(С) := ®'я(с) п ^¡я](С) - {Р е & (С): я'(Р) < я, я'(Р) < я}
есть класс аппроксимирующих многогранников с ограничением сложности гранной структуры: числа вершин и гиперграней одновременно, т.е. первого и последнего компонентов вектора чисел граней (или /-вектора, см. [27]). Пусть
5(С, ^{я}) := тОДС, Р): Р е я}(С)}. Из [5] для С е % + и ё> 4 вытекают следующие оценки на эту величину:
2/( d -п d
2
\ 2/(d - 1)
Иш М5(С, ^{я})я2/(d-1) > -£-1 Гкс(х)1/2da(x) я 34ея1 J
дС
С ^2/(d -1)
ИшБир5(С, ^{я})я2/(d 1) < сош^ [кС(х) 1/2da(x)
я ^ ю ^ ^
дС
(4)
(5)
Оценки (4), (5), в отличие от (2), (3), не являются асимптотически точными, причем верхняя оценка (5) содержит не определенную явно константу. Заметим, что метод доказательства, использованный в [5], не позволяет для конкретного выпуклого тела явно конструировать аппроксимирующие многогранники, обладающие соответствующими свойствами.
При ё = 2 числа вершин и граней (т.е. ребер) многоугольника совпадают и поэтому для
5(С, я} (С)) могут быть использованы асимптотики (2) и (3). В [6] в случае ё = 3 получена асимптотика для ограничения по числу ребер (1-мерных граней). Из формулы Эйлера, связывающей числа вершин, ребер и граней трехмерного выпуклого многогранника, следуют в этом случае утверждения, аналогичные (4) и (5) и для ё = 3.
2
Таким образом, для С е % + при ё > 2 справедливы оценки
5(С, ®\я))< ^, (6)
я
5( С, я} )<с-°п;^. (7)
я
Верхняя оценка (1) справедлива для всего класса выпуклых тел %. Верхняя оценка (6) справедлива только для класса % + . Из гипотезы Грубера (см. [5]) следует предположение о справедливости (6) для всего класса %. Это предположение остается открытым.
3. Рассмотрим теперь одну из общих аппроксимационных схем — схему восполнения (см. [13], [14], [20]).
СХЕМА ВОСПОЛНЕНИЯ
Пусть построен Pn е ¥ (С). Тогда (n + 1)-я итерация состоит из двух шагов.
Шаг 1. Выбираемpn е дС.
Шаг 2. Положим Pn + 1 := conv{pn, Pn}.
Конкретные методы, основанные на схеме восполнения, можно характеризовать способами решения двух задач: способом выбораpn е дС и способом построения Pn + 1 := conv{pn, Pn} в виде, требуемом для продолжения итераций. Такие методы мы будем называть методами восполнения.
Если в некотором методе восполнения многогранник н
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.