1. На главную
  2. Электронные версии
  3. Журнал вычислительной математики и математической физики
  4. T. 59, № 7, 2019

Журнал вычислительной математики и математической физики, 2019, T. 59, № 7, стр. 1264-1274

Сложность методов аппроксимации выпуклых компактных тел многогранниками двойного описания и ее оценки для гипершара

Р. В. Ефремов *

Universidad Rey Juan Carlos
28933 Móstoles, MadridEspaña

* E-mail: roman.efremov@urjc.es

Поступила в редакцию 20.10.2018
После доработки 14.02.2019
Принята к публикации 11.03.2019

Полный текст (PDF)

Аннотация

В статье, на примере аппроксимации шара, приводится сравнительный анализ сложности подходов к построению аппроксимации выпуклых компактных тел многогранниками двойного описания. В частности, получена оценка сложности Метода уточнения оценок для случая аппроксимации многомерного шара. Библ. 39.

Ключевые слова: полиэдральная аппроксимация выпуклых тел, многогранник двойного описания, многомерный шар, оценка сложности метода, покрытие многомерной единичной сферы, Метод уточнения оценок.

1. ВВЕДЕНИЕ

Задача аппроксимации выпуклых тел многогранниками имеет большой теоретический и прикладной интерес. Среди методов полиэдральной аппроксимации выпуклых тел выделяются методы, основанные на многогранниках двойного описания [1]: описания многогранников как в форме пересечения конечного множества полупространств, соответствующих граням многогранника, так и в форме множества всех выпуклых комбинаций экстремальных точек, соответствующих вершинам многогранника. Это двойное представление полезно в тех приложениях, где необходимо иметь одновременно связную информацию как о самих данных, так и об их “форме”, например, при визуализации и интерактивном исследовании многомерных числовых данных [2].

Задача аппроксимация выпуклых тел многогранниками двойного описания подразумевает, вообще говоря, решение двух независимых задач: задачи аппроксимации выпуклого тела и задачу представления этой аппроксимации в виде многогранника двойного описания. Хотя можно предложить методы, в которых обе задачи будут решаться одновременно, в целях анализа методов имеет смысл рассмотреть сначала эти две задачи отдельно.

Проблема полиэдральной аппроксимации изначально формулируется следующим образом [3]: для выпуклого компактного тела (ВКТ) C необходимо построить многогранник с n вершинами (или n гранями), который аппроксимирует тело оптимально в заданной метрике. Многогранник считается построенным, если заданы координаты его вершин и/или задана система линейных неравенств, соответствующих его граням. В такой постановке задача решается для особых выпуклых тел, и только в плоском случае [3]. В [4], [5] для произвольной размерности доказано существование асимптотически оптимальных последовательностей вершин вписанных и гиперграней описанных многогранников при аппроксимации ВКТ с достаточно гладкой поверхностью. Тем не менее для множеств размерности более двух не существует конструктивных методов для построения таких последовательностей. Другой подход, часто используемый в приложениях для аппроксимации выпуклых тел, основан на использовании (неадаптивных) покрытий поверхностей этих тел окрестностями конечного числа точек, выбранных заранее, или случайным образом [3], [6], [7]. Например, сеть в полярных координатах для аппроксимации многомерной сферы точками изучена в [8]. Узлы таких сетей могут быть использованы в качестве направлений, по которым строятся гиперграни многогранника, аппроксимирующего соответствующее тело.

Говорят, что алгоритм решает задачу перечисления вершин, если он преобразует представление в виде пересечения полупространств (соответствующих граням многогранника) в представление в виде выпуклой оболочки конечного множества точек (соответствующих вершинам), в то время как алгоритм, который выполняет преобразование в противоположном направлении, решает проблему перечисления граней. Существуют алгоритмы преобразования одного описания многогранника в другой [9]. Преобразования в обоих направлениях вычислительно эквивалентны, т.е. соответствующие проблемы сводимы одна к другой за линейное время [9].

Термин многогранник двойного описания связан с одноименным методом [1], хотя более общий метод был предложен еще в [10]. Тем не менее метод [10], который решает задачу перечисления граней, неэффективен с вычислительной точки зрения, так как он генерирует много избыточных полупространств. В [1] были предложены идеи, которые позволяют значительно сократить количество избыточных полупространств. Эти идеи были переформулированы и формально доказаны в [11]. На основе этих идей в [12] предложены методы, позволяющие генерировать значительно меньше избыточных полупространств по сравнению с методом [10]. Однако эти методы не гарантируют, что множество полупространств не является избыточным [2] и что задачи с таким числом полупространств являются вычислительно разрешимыми [13]. Кроме того, вычислительная сложность этих методов является чувствительной к порядку, в котором обрабатываются входные данные, а именно, вершины многогранника в случае задачи перечисления граней. Проблема устранения зависимых неравенств в линейных системах исследуется, в частности, в [13], [14] и [15]. Тем не менее основной недостаток подхода, основанного на [10] сохраняется: нет никакой гарантии того, что соответствующие вычислительные процедуры завершатся точным решением задачи перечисления граней. Кроме того, промежуточный результат, к которому они приходят в случае невозможности продолжения вычислений, вообще говоря, не будет иметь ничего общего с решением задачи перечисления граней [16]. Помимо указанных выше, существует целый ряд методов, разработанных для решения задач перечисления вершин (гиперграней) многогранников, которые основаны на идеях, схожих с [1]. Эти методы составляют класс итеративных методов, к которым, в частности, относится известный Метод под-над (МПН) [17]–[19]. Другой большой класс методов составляют методы обхода комбинаторной структуры многогранника, к которым, в частности, относится Метод заворачивания подарка (МЗП) [20]. В целом методы перечисления граней (вершин) многогранников исчерпываются двумя вышеуказанными общими классами [9]. Обзор методов можно найти, например, в [9]. В [21] предложен метод, для которого была получена следующая оценка сложности по времени построения выпуклой оболочки:

(1)
${{T}_{{{\text{CH}}}}}(d,N) = O({{N}^{{[d/{\text{2]}}}}}),$
где N – число точек, а d – размерность пространства. Нам неизвестны алгоритмы, для которых оценка (1) была бы улучшена в общем случае. Поэтому мы примем (1) в качестве оценки сложности задачи построения выпуклой оболочки.

В [22] для задачи перечисления граней предлагается искать аппроксимацию соответствующего выпуклого многогранника. Метод [22] генерирует последовательность многогранников двойного описания, сходящуюся к аппроксимируемому многограннику. При этом последовательность многогранников строится адаптивно, с учетом границы аппроксимируемого многогранника. Кроме того, верхняя оценка точности аппроксимации, вычисляемая в так называемой псевдометрике направлений [23], для которой известны теоретические оценки, связывающие ее с хаусдорфовым расстоянием между аппроксимируемым и аппроксимирующим телами, известна в любой момент процесса аппроксимации. Таким образом, если на определенной итерации вычислительный процесс не может продолжаться, например, по причине достижения предела вычислительной мощности, то за результат процесса аппроксимации может быть принят многогранник, полученный на последней успешной итерации, причем будет известна оценка точности аппроксимации. Если же вычислительный процесс не прерывается, то исходная задача решается точным образом. В качестве альтернативы такому развитию событий требуемая точность аппроксимации может быть задана до начала вычислительного процесса, и процесс аппроксимации будет считаться завершенным, как только будет достигнута эта точность. Идеи метода [22] были использованы впоследствии для общего случая задачи аппроксимации ВКТ, заданного своей опорной функцией [23], [24]. В [24]–[26] предложен Метод уточнения оценок (УО), который реализует общую схему [23].

В [26] доказано, что для любого гладкого тела алгоритм УО дает оптимальный порядок скорости сходимости для грани любой размерности, а в [27] показано, что точность метода УО в гладком случае асимптотически не хуже, чем в 4 раза по сравнению с оптимальной. Для случая многомерного шара этот результат усилен в [28], [29], в том числе получены константы сходимости для малых размерностей.

Итак, в целом можно выделить два основных подхода к решению задачи аппроксимации ВКТ многогранниками двойного описания. Первый подход заключается в последовательном решении двух задач: генерации точек, покрывающих поверхность аппроксимируемого выпуклого множества, и последующей генерации выпуклой оболочки этих точек. Условно назовем этот подход последовательным. Второй подход заключается в итеративной аппроксимации поверхности ВКТ адаптивной сетью точек и прогрессивном построении их выпуклой оболочки. Условно назовем этот подход прогрессивным.

Поставим задачу эффективного построения двойственного описания полиэдральной аппроксимации ВКТ как задачу аппроксимации ВКТ последовательностью многогранников, которые бы имели одновременно оптимальный порядок скорости сходимости как по числу граней, так и по числу вершин. Метод УО решает поставленную задачу [27], [29]. В данной работе мы исследуем алгоритмическую сложность задачи построения двойственного описания полиэдральной аппроксимации ВКТ на примере аппроксимации многомерного единичного шара. Нашей целью является сравнение последовательного и прогрессивного подходов к решению этой задачи.

В дальнейшем мы будем следовать следующему плану изложения. В разд. 2 приведена постановка задачи сравнения методов аппроксимации выпуклых компактных тел многогранниками двойного описания. В разд. 3 формулируется метод построения двойного описания аппроксимации шара многогранником наилучшей аппроксимации и исследуется его сложность. В разд. 4 исследуется метод аппроксимации шара многогранником двойного описания с вершинами в узлах неадаптивной сетки. В разд. 5 оценка сложности при аппроксимации шара получена для Метода УО. В разд. 6 приводится сравнительный анализ сложности методов, исследованных в предыдущих разделах. В завершение статьи приведено обсуждение полученных результатов.

2. ПОСТАНОВКА ЗАДАЧИ СРАВНЕНИЯ МЕТОДОВ АППРОКСИМАЦИИ ВЫПУКЛЫХ КОМПАКТНЫХ ТЕЛ МНОГОГРАННИКАМИ ДВОЙНОГО ОПИСАНИЯ

Пусть ${{\mathbb{R}}^{d}}$ есть d-мерное евклидово пространство с обычным скалярным произведением, нормой $\left\| {\, \cdot \,} \right\|$ и метрикой $\rho ( \cdot , \cdot )$. Обозначим через $\mathcal{C}$ класс выпуклых компактных множеств с непустой внутренностью, т.е. выпуклых компактных тел (ВКТ). На $\mathcal{C}$ рассмотрим метрику Хаусдорфа:

$\delta ({{C}_{{\text{1}}}},{{C}_{{\text{2}}}}): = {\text{max}}\{ {\text{sup}}\{ \rho (x,{{C}_{{\text{2}}}}):x \in {{C}_{{\text{1}}}}\} ,{\text{sup}}\{ \rho (x,{{C}_{{\text{1}}}}):x \in {{C}_{{\text{2}}}}\} \} .$

Пусть $\mathcal{P},\;\mathcal{P} \subset \mathcal{C}$, – класс выпуклых телесных многогранников (выпуклых оболочек конечного множества точек, не лежащих в одной гиперплоскости). Для $P \subset \mathcal{P}$ через Mt(P) обозначим множество его вершин (граней нулевой размерности), а через mt(P) – число его вершин, через M f(P) обозначим множество векторов единичных внешних нормалей к его гиперграням (граням размерности (d – 1)), а через m f(P) – число его гиперграней. Через ∂C обозначим границу тела С. Для $C \subset \mathcal{C}$ через $\mathcal{P}(C)$, где $\mathcal{P}(C) \subset \mathcal{P}$, обозначим класс вписанных в C многогранников, т.е. многогранников, чьи вершины лежат на поверхности ∂C.

Под методом аппроксимации ВКТ C многогранниками двойного описания будем понимать метод, который для некоторого $C \subset \mathcal{C}$ и любого заданного h > 0 строит двойное описание многогранника P ∈ $\mathcal{P}$ такого, что $\delta (P,C) \leqslant h$. В данной работе в качестве аппроксимируемого ВКТ мы рассмотрим многомерные единичные шары B d = {||x|| ≤ 1: x ∈ ${{\mathbb{R}}^{d}}$} произвольной размерности d. Под сложностью T(d, h) метода будем понимать алгебраическую временную сложность [30] совокупности операций, необходимых для построения P. Под задачей сравнения методов аппроксимации ВКТ многогранниками двойного описания будем понимать задачу сравнения T(d, h) при заданных d и h.

3. МЕТОД ПОСТРОЕНИЯ ДВОЙНОГО ОПИСАНИЯ АППРОКСИМАЦИИ ШАРА МНОГОГРАННИКОМ НАИЛУЧШЕЙ АППРОКСИМАЦИИ И ЕГО СЛОЖНОСТЬ

Обозначим через ${{\mathcal{P}}_{m}}(C)$ множество $\{ P \in \mathcal{P}(C):{{m}^{t}}(P) \leqslant m\} $. Обозначим $\delta (C,{{\mathcal{P}}_{m}}(C)) = $ $ = {\text{inf}}\{ \delta (C,P):P \in {{\mathcal{P}}_{m}}(C)\} $. Известно [31], что многогранник ${{P}_{m}}(C) \in {{\mathcal{P}}_{m}}(C)$ такой, что $\delta (C,{{P}_{m}}(C)) = \delta (C,{{\mathcal{P}}_{m}}(C))$ всегда существует; назовем его многогранником наилучшей аппроксимации [31] с не более, чем m вершинами. Тем не менее конструктивные способы построения последовательностей ${{\{ {{P}_{m}}(C)\} }_{m}}_{{ = d + 1,d + 2, \ldots }}$ существуют только для некоторых двумерных тел: способы построения таких последовательностей в общем случае не известны. Предположим известными последовательности Mt(Pm(B d)), m ≥ d + 1, и точности $\delta ({{B}^{d}},{{P}_{m}}({{B}^{d}}))$, m ≥ d + 1.

Рассмотрим гипотетический метод аппроксимации шара B d многогранником двойного описания, который, для заданной точности h, строит многогранник Pm*(B d) такой, что $\delta ({{B}^{d}},{{P}_{{m*}}}({{B}^{d}})) \leqslant h$. Предполагается, что для построения многогранника используется один из методов построения выпуклой оболочки с оценкой сложности не хуже, чем (1). Обозначим этот метод через ТМ (теоретический метод). Исследуем его сложность.

Лемма 1. Пусть ${{m}_{{{\text{opt}}}}}(d,h) = \min \{ m:\delta ({{B}^{d}},{{P}_{m}}({{B}^{d}})) \leqslant h\} $. Тогда

(2)
${{m}_{{{\text{opt}}}}}(d,h) = O\left( {{{{\left( {\frac{1}{h}} \right)}}^{{\frac{{d - 1}}{2}}}}{{2}^{{\frac{{1 - d}}{2}}}}{{d}^{{\frac{3}{2}}}}\ln d} \right).$

При доказательстве леммы используем следующий результат [29]:

(3)
$\mathop {\lim }\limits_{m \to \infty } \delta ({{B}^{d}},{{\mathcal{P}}_{m}}({{B}^{d}})){{m}^{{2/(d - 1)}}} = \frac{1}{2}{{\left( {{{\vartheta }_{{d - 1}}}\frac{{d{{\pi }_{d}}}}{{{{\pi }_{{d - 1}}}}}} \right)}^{{2/(d - 1)}}},$
где ${{\vartheta }_{d}}$ есть плотность редчайшего покрытия пространства ${{\mathbb{R}}^{d}}$ шарами фиксированного радиуса [32], а ${{\pi }_{d}} = {{\pi }^{d}}^{{/{\text{2}}}}{\text{/}}\Gamma \left( {\left( {d{\text{/2}}} \right) + {\text{1}}} \right)$ – объем единичного шара в ${{\mathbb{R}}^{d}}$.

Доказательство леммы 1. Из (3) следует, что

(4)
${{m}_{{{\text{opt}}}}}(d,h) = O\left( {{{{\left( {\frac{1}{{2h}}} \right)}}^{{\frac{{d - 1}}{2}}}}{{\vartheta }_{{d - 1}}}\frac{{d{{\pi }_{d}}}}{{{{\pi }_{{d - 1}}}}}} \right).$

Из [28, с. 1245], известно, что

(5)
$\frac{{{{\pi }_{d}}}}{{{{\pi }_{{d - 1}}}}} \leqslant {{\left( {\frac{{2\pi }}{d}} \right)}^{{1/2}}}{\kern 1pt} ,\quad d \geqslant 2,$
а в [32] приведена оценка ${{\vartheta }_{d}} \leqslant {\text{ }}d\ln d + d\ln \ln d + {\text{5}}d$, откуда следует, что

(6)
${{\vartheta }_{d}} = ({\text{1}} + o({\text{1}}))d\ln d.$

Таким образом, с учетом (5) и (6), оценку (4) можно переписать в виде (2).

Теорема 1. Для сложности Метода ТМ справедлива следующая оценка:

(7)
${{T}_{{{\text{TM}}}}}(d,h) = O\left( {{{{\left( {\frac{1}{h}} \right)}}^{{\frac{{d - 1}}{2}\left\lfloor {\frac{d}{2}} \right\rfloor }}}{{{\left( {{{2}^{{\frac{{1 - d}}{2}}}}{{d}^{{\frac{3}{2}}}}\ln d} \right)}}^{{\left\lfloor {\frac{d}{2}} \right\rfloor }}}} \right).$

Доказательство. Оценка (7) получена непосредственно из (1) и (2).

4. МЕТОД АППРОКСИМАЦИИ ШАРА МНОГОГРАННИКОМ ДВОЙНОГО ОПИСАНИЯ С ВЕРШИНАМИ В УЗЛАХ ПРОСТОЙ НЕАДАПТИВНОЙ СЕТКИ И ОЦЕНКА ЕГО СЛОЖНОСТИ

Рассмотрим на S d – 1 внутреннюю метрику ρ', совпадающую с минимальным углом между векторами, направленными на точки сферы, т.е. с минимальной длиной дуги большого круга (сечения сферы двумерной плоскостью, проходящей через ее центр и рассматриваемые точки).

Пусть T – конечное подмножество множества S d – 1. Пусть Uε(T) – замкнутая ε-окрестность подмножества T. Если S d – 1 ⊆ Uε(T), то Uε(T) будем называть (конечным) покрытием S d – 1, а T – базой покрытия. Радиусом покрытия S d – 1 будем называть величину ε(T) := inf{ε : S d – 1 ⊆ Uε(T)}.

Пусть Ωk – совокупность подмножеств S d – 1, составленных из k > 0 точек. Bведем обозначение $\varepsilon _{k}^{{{\text{opt}}}}: = \inf \{ \varepsilon (T):T \in {{\Omega }_{k}}\} $. Как показано в [7], для S d – 1 и любого k существует оптимальное k-точечное покрытие S d – 1 с базой $T_{k}^{{{\text{opt}}}}$ ∈ Ωk, на которой достигается величина $\varepsilon _{k}^{{{\text{opt}}}}$, однако способы построения $T_{k}^{{{\text{opt}}}}$ до сих пор неизвестны. Неизвестны также и значения $\varepsilon _{k}^{{{\text{opt}}}}$ для произвольного k. Заметим, что можно получить совпадающую с (7) оценку для сложности построения многогранника двойного описания с помощью оптимального покрытия сферы $T_{k}^{{{\text{opt}}}}$. В [6], [7] предложен способ построения субоптимальных покрытий S d – 1, т.е. таких покрытий Tk, для которых величина ${{\eta }_{d}} = \mathop {\lim }\limits_{k \to 0} \left( {{{\varepsilon _{k}^{{{\text{opt}}}}} \mathord{\left/ {\vphantom {{\varepsilon _{k}^{{{\text{opt}}}}} {\varepsilon ({{T}_{k}})}}} \right. \kern-0em} {\varepsilon ({{T}_{k}})}}} \right)$, называемая асимптотической эффективностью покрытия Tk, строго больше 0. Показано, что асимптотическая эффективность растет с ростом d, и делается гипотеза о том, что построенные покрытия асимптотически оптимальны. В [33] предлагаются методы, которые используют такие покрытия для аппроксимации одного класса выпуклых тел.

Тем не менее на практике обычно используются покрытия, далекие от оптимальных, в частности, широкое распространение получили покрытия, получаемые на основе многомерных полярных координат [34]. Поскольку одной из целей данной статьи является получение оценок сложности методов не эффективных, но широко используемых на практике, мы приводим здесь анализ метода аппроксимации шара многогранником двойного описания с вершинами в узлах покрытия сферы, получаемого на основе многомерных полярных координат.

Рассмотрим сферическую систему координат в ${{\mathbb{R}}^{d}}$ (см. [35])

(8)
$\begin{gathered} {{x}_{1}} = r\prod\limits_{i = 1}^{d - 1} {\sin {{\alpha }_{i}}} , \\ {{x}_{k}} = r\cos {{\alpha }_{{k - 1}}}\prod\limits_{i = k}^{d - 1} {\sin {{\alpha }_{i}}} , \\ {{x}_{d}} = r\cos {{\alpha }_{{d - 1}}}, \\ \end{gathered} $
в которой r ≥ 0, а сферические углы α1, α2, …, αd – 2 изменяются в пределах 0 ≤ αi < π и 0 ≤ αd – 1 < 2π. Тогда S d – 1 задается соотношением (8) при r = 1.

Пусть

$\Psi = \left( {\prod\limits_{i = 1}^{d - 1} {\sin {{\alpha }_{i}},...,\cos {{\alpha }_{{k - 1}}}} \prod\limits_{i = 1}^{d - 1} {\sin {{\alpha }_{i}}} ,\cos {{\alpha }_{{d - 1}}}} \right).$

Под сетью, порождаемой сферическими координатами на единичной сфере S d – 1, будем понимать конечное множество S d – 1:

(9)
${{T}^{{{\text{Sph}}}}} = \{ \Psi :{{\alpha }_{i}} = {{s}_{i}}{{\gamma }_{i}},\;{{s}_{i}} = 0,{\text{1}},...,{{S}_{i}},\;i = {\text{1}},{\text{2}},...,d - {\text{2}},\;{{\alpha }_{d}}_{{ - {\text{1}}}} = l\alpha ,\;l = 0,{\text{1}},...,L\} ,$
где
${{S}_{i}} = \left[ {\frac{\pi }{{{{\gamma }_{i}}}}} \right],\quad i = {\text{1}},....,d - {\text{2}},\quad L = \left[ {\frac{{2\pi }}{\alpha }} \right]$
суть натуральные числа, причем углы γi, i = 1, …, d – 2, и α удовлетворяют следующим условиям:

$0 < {{\gamma }_{i}} < \frac{\pi }{4},\quad i = 1,...,d--2,\quad 0 < \alpha < \frac{\pi }{4}.$

Обозначим через $T_{{k,d}}^{{{\text{Sph}}}}$ сеть (9) мощности k, для которой γ1 = γ2 = … = γd – 2 = γ = α. Пусть ${{k}_{{{\text{Sph}}}}}(d,\varepsilon ) = \min \{ k:\varepsilon (T_{{k,d}}^{{{\text{Sph}}}}) \leqslant \varepsilon \} $. В [8] была получена следующая оценка:

(10)
$\mathop {\lim }\limits_{\varepsilon \to \infty } [{{\varepsilon }^{{d - 1}}}{{k}_{{{\text{Sph}}}}}(d,\varepsilon )] = \frac{{{{\pi }^{{d - 1}}}{{{(d - 1)}}^{{\frac{{d - 1}}{2}}}}}}{{{{2}^{{d - 2}}}}},$
где ε – заданный радиус покрытия сетью $T_{{k,d}}^{{{\text{Sph}}}}$ сферы S d – 1.

Обозначим через $P_{{k,d}}^{{{\text{Sph}}}}$ многогранник с вершинами в точках сферы S d – 1, принадлежащих базе покрытия $T_{{k,d}}^{{{\text{Sph}}}}$. Предположим известными точности $\delta ({{B}^{d}},P_{{k,d}}^{{{\text{Sph}}}})$, k ≥ d + 1. Рассмотрим метод аппроксимации шара B d многогранником двойного описания, который, для заданной точности h, строит многогранник $P_{{k,d}}^{{{\text{Sph}}}}$ такой, что $\delta ({{B}^{d}},P_{{k,d}}^{{{\text{Sph}}}}) \leqslant h$. Обозначим этот метод через СферМ (СМ). Исследуем его сложность.

Лемма 2. Пусть ${{m}_{{{\text{Sph}}}}}(d,h) = \min \{ k:\delta ({{B}^{d}},P_{{k,d}}^{{{\text{Sph}}}}) \leqslant h\} $. Тогда

(11)
${{m}_{{{\text{Sph}}}}}(d,h) = O\left( {{{{\left( {\frac{1}{h}} \right)}}^{{\frac{{d - 1}}{2}}}}{{{\left( {{{{\left( {\frac{\pi }{{2\sqrt 2 }}} \right)}}^{2}}(d - 1)} \right)}}^{{\frac{{d - 1}}{2}}}}} \right).$

Доказательство. Из (10) следует

(12)
${{k}_{{{\text{Sph}}}}}(d,\varepsilon ) = O\left( {{{{\left( {\frac{\pi }{2}} \right)}}^{{d - 1}}}{{{(d - 1)}}^{{\frac{{d - 1}}{2}}}}{{\varepsilon }^{{1 - d}}}} \right).$

Пусть Pk – выпуклый телесный многогранник с k вершинами в точках сферы S d – 1, принадлежащих базе покрытия Tk. В [6] указана связь между ε(Tk) и расстоянием по Хаусдорфу hk между Pk и шаром B d : hk = 1 – cos(ε(Tk)).

Таким образом, при k → ∞ справедливо ε(Tk) ≈ (2hk)1/2, в частности,

(13)
$\varepsilon ({{T}_{k}}) = O({{(2{{h}_{k}})}^{{1/2}}}).$

Из (12) и (13) следует (11).

Теорема 2. Для алгебраической сложности метода СМ справедлива следующая оценка:

(14)
${{T}_{{{\text{С ф е р М }}}}}\left( {d,h} \right) = O\left( {{{{\left( {\frac{1}{h}} \right)}}^{{\frac{{(d - 1)}}{2}\left\lfloor {\frac{d}{2}} \right\rfloor }}}{{{\left( {{{{\left( {\frac{\pi }{{2\sqrt 2 }}} \right)}}^{2}}(d - 1)} \right)}}^{{\frac{{(d - 1)}}{2}\left\lfloor {\frac{d}{2}} \right\rfloor }}}} \right).$

Доказательство. Оценка (14) получена непосредственно из (1) и (11).

5. МЕТОД УО И ОЦЕНКА ЕГО СЛОЖНОСТИ ПРИ АППРОКСИМАЦИИ ШАРА

Дадим описание метода УО в терминах операций, для которых могут быть получены оценки вычислительной сложности.

Метод УО аппроксимации ВКТ

До начала работы основной части метода будем предполагать построенным d – мерный симплекс начальной аппроксимации ${{P}^{0}} \in \mathcal{P}(C)$. Детали построения P 0 можно найти в [16].

Пусть построено аппроксимирующее множество ${{P}^{n}} \in \mathcal{P}(C)$. Обозначим через ΔM  f(P n) множество векторов единичных внешних нормалей гиперграней, добавленных к P n – 1 при построении P n на итерации n. Пусть задана точность εp аппроксимации. Опишем итерацию n + 1.

Шаг 1.

1.1. Для каждого ui ∈ ΔM f(P n) найти

1.1.1. Оценочную вершину pi = argmax{〈ui, x〉 | x ∈ C},

1.1.2. Невязку оценочной вершины pi : δn(i) = 〈ui, pi〉 – g(ui, P n).

1.2. Найти грань, на которой достигается максимальная невязка:

$n{\kern 1pt} * = \operatorname{argmax} \{ {{\delta }_{n}}(i)\,|\,i \in {{m}^{f}}({{P}^{n}})\} .$

1.3. Если δn(n*) ≤ εp, то заданная точность аппроксимации достигнута, иначе перейти на Шаг 2.

Шаг 2. Построить описание P n + 1:= conv{pn*, P n} в виде системы линейных неравенств, характеризующих множество M f(P n + 1).

Перейдем к оценке сложности УО при аппроксимации шара B d. Для оценки сложности шага 2 в данной статье воспользуемся оценками, полученными для Метода ПН построения выпуклой оболочки точек [18], поскольку этот метод обладает свойством открытости: точки выпуклой оболочки могут поступать на вход соответствующего алгоритма последовательно – знания всех таких точек до начала работы метода не требуется. Приведем описание (n + 1)-й итерации Метода ПН на содержательном уровне: пусть построена выпуклая оболочка P первых n точек, mt(P) = n > d. Тогда при присоединении очередной точки p, внешней к P, строится опорный “конус видимости” множества P, и удаляется часть оболочки P, “затеняемая” данным конусом (при этом использование терминов “конус видимости” и “затенение” используется по аналогии с трехмерным случаем).

Лемма P1 (см. [18]). Полное время операции присоединения вершины к многограннику P, mt(P) = = n > d в Методе ПН есть

(15)
$T(d) = O({{m}^{f}}(P)).$

Следствие 1. Оценка (15) есть оценка сложности по времени построения опорного “конуса видимости” множества P n на шаге 2 итерации n ≥ 0 алгоритма УО.

Доказательство. Действительно, поскольку в методе УО mt(P 0) = d + 1, mt(P n) ≥ mt(P 0) для любого n ≥ 0, то (15) справедлива для любого n ≥ 0.

Пусть теперь ${{\{ {{P}^{m}}\} }_{m}}_{{ = 1,2,...}}$ – последовательность многогранников, порождаемая методом УО для B d. В [29] получена следующая асимптотическая оценка:

(16)
$\mathop {\lim }\limits_{m \to \infty } \delta ({{B}^{d}},{{P}^{m}}){{m}^{{2/(d - 1)}}} = 2{{\left( {{{\delta }_{{d - 1}}}\frac{{d{{\pi }_{d}}}}{{{{\pi }_{{d - 1}}}}}} \right)}^{{2/(d - 1)}}},$
где δd есть плотность максимальной упаковки пространства ${{\mathbb{R}}^{d}}$ шарами фиксированного радиуса [32].

Лемма 3. Пусть ${{m}_{{У О }}}(d,h) = \min \{ m:\delta ({{B}^{d}},{{P}^{m}}) \leqslant h\} $. Тогда

(17)
${{m}_{{У О }}}(d,h) = O\left( {d{{{\left( {\frac{2}{h}} \right)}}^{{\frac{{d - 1}}{2}}}}} \right).$

Доказательство. Из (16) следует, что

(18)
${{m}_{{У О }}}(d,h) = O\left( {{{{\left( {\frac{2}{h}} \right)}}^{{\frac{{d - 1}}{2}}}}{{\delta }_{{d - 1}}}\frac{{d{{\pi }_{d}}}}{{{{\pi }_{{d - 1}}}}}} \right).$

С учетом δd ≤ 1 (см. [32]) и (5), оценку (18) можно переписать в виде (17).

Обозначим через Π+ множество граней P n, затеняемых конусом видимости из вершины pn* в описании метода УО, через T(n) – множество вершин множества Π+, mn = card(T(n)) – число элементов множества T(n). В частности, в [28] для mn при аппроксимации единичного d-мерного шара B d получена следующая оценка:

Лемма K1. При аппроксимации методом УО шара B d

(19)
${{m}_{n}} = O({{{\text{2}}}^{{{\text{1}}.{\text{43}}0{\text{5}}(d - {\text{1}})}}}).$

Обозначим через $\Delta f_{n}^{{d - 1}}$ число новых гиперграней аппроксимирующего многогранника, образованных на n-й итерации метода УО при аппроксимации шара B d.

Лемма 4. Пусть ${{\{ {{P}^{n}}\} }_{n}}_{{ = 1,2, \ldots }}$ – последовательность многогранников, построенных методом УО при аппроксимации шара B d. Тогда

(20)
$\Delta f_{n}^{{d - 1}} = O({{2}^{{0.71525{{d}^{2}}}}}).$

Доказательство. В [28] величину $\Delta f_{n}^{{d - 1}}$ предлагается оценивать сверху максимальным числом гиперграней, которые можно натянуть на множество точек T(n) ∪{pn}. Используя оценку (12) из [28], можно оценку $\Delta f_{n}^{{d - 1}}$ записать в следующем виде:

(21)
$\Delta f_{n}^{{d - 1}} = O({{(m{}_{n} + 1)}^{{\left\lfloor {d/2} \right\rfloor }}}).$

Из (19), (21) получим оценку (20).

Следствие 2. Оценку (20) можно использовать для оценки сложности по времени операции удаления граней Π+ на шаге 2 итерации n алгоритма УО.

Доказательство. Действительно, число граней из Π+ можно оценить сверху максимальным числом гиперграней, которые можно натянуть на множество точек T(n). Отсюда и из хода доказательства леммы 4 получаем утверждение следствия.

В [28] для m f(P n) при аппроксимации шара B d получена следующая оценка:

Лемма K2. При аппроксимации методом УО шара B d

(22)
${{m}^{f}}({{P}^{n}}) = O\left( {{{h}^{{\frac{{1 - d}}{2}}}}{{2}^{{0.71525{{d}^{2}}}}}} \right).$

Заметим, что (22) не зависит от n.

Теорема 3. Сложность метода УО при аппроксимации шара B d с точностью h в смысле хаусдорфова расстояния равна

(23)
${{T}_{{У О }}}(d,h) = O\left( {{{{\left( {\frac{1}{h}} \right)}}^{{(d - 1)}}}2{}^{{{\text{0}}{\text{.71525}}{{d}^{{\text{2}}}} + d/2}}{{d}^{3}}} \right).$

Доказательство. Сложностью шага 1.1 при аппроксимации шара можно пренебречь, так как pi = ui и δn(i) = 1 – di, где di – правая часть нормального уравнения гиперплоскости 〈ui, x〉 = di. На шаге 1.2 УО решается задача сортировки H(P n): образованные на предыдущей итерации n–1 грани встраиваются в сортированный список остальных граней за время TСОРТ(n) = = O($\Delta f_{n}^{{d - 1}}$log(m f(P n))). Обозначим TСОРТ_УО сложность шага 1 УО. Тогда, используя оценки (17), (20) и (22), получаем

(24)
$\begin{gathered} {{T}_{{{\text{С О Р Т }}\_{\text{У О }}}}}(d,h) = \sum\limits_{n = 0}^{{{m}_{{ER}}}(d,h)} {{{T}_{{{\text{С О Р Т }}}}}(n)} < \left( {m_{{{\text{У О }}}}^{{}}(d,h) + 1} \right){{T}_{{{\text{С О Р Т }}}}}\left( {{{m}_{{{\text{У О }}}}}(d,h)} \right) = \\ = \;O\left( {d{{{\left( {\frac{2}{h}} \right)}}^{{\frac{{d - 1}}{2}}}}2{}^{{{\text{0}}{\text{.71525}}{{d}^{{\text{2}}}}}}\log \left( {{{h}^{{\frac{{1 - d}}{2}}}}{{2}^{{0.71525{{d}^{2}}}}}} \right)} \right) = O\left( {{{{\left( {\frac{1}{h}} \right)}}^{{\frac{{d - 1}}{2}}}}\log \frac{1}{h}2{}^{{{\text{0}}{\text{.71525}}{{d}^{{\text{2}}}} + d/2}}{{d}^{3}}} \right). \\ \end{gathered} $

Для оценки шага 2 УО используем вместе следствия 1 и 2 и оценки (17) и (22):

(25)
$\begin{gathered} {{T}_{{{\text{В Ы П }}\_{\text{У О }}}}}(d,h) = \sum\limits_{m = 0}^{{{m}_{{ER}}}(d,h)} {\left( {{{T}_{m}}{\text{(}}d{\text{)}} + \Delta f_{m}^{{d - 1}}} \right)} < \left( {m_{{{\text{У О }}}}^{{}}(d,h) + 1} \right)\left( {{{T}_{{{{m}_{{{\text{У О }}}}}(d,h)}}}\left( d \right) + \Delta f_{{{{m}_{{{\text{У О }}}}}(d,h)}}^{{d - 1}}} \right) = \\ = \;O\left( {d{{{\left( {\frac{2}{h}} \right)}}^{{\frac{{d - 1}}{2}}}}{{h}^{{\frac{{1 - d}}{2}}}}{{2}^{{0.71525{{d}^{2}}}}}} \right) = O\left( {{{{\left( {\frac{1}{h}} \right)}}^{{(d - 1)}}}{{2}^{{0.71525{{d}^{2}} + d/2}}}d} \right). \\ \end{gathered} $

Сравнивая (24) и (25), запишем сложность метода УО в виде (23)

${{T}_{{{\text{У О }}}}}(d,h) = {{T}_{{{\text{С О Р Т }}\_{\text{У О }}}}}(d,h) + {{T}_{{{\text{В Ы П }}\_{\text{У О }}}}}(d,h) = O\left( {{{{\left( {\frac{1}{h}} \right)}}^{{(d - 1)}}}2{}^{{{\text{0}}{\text{.71525}}{{d}^{{\text{2}}}} + d/2}}{{d}^{3}}} \right).$

6. СРАВНЕНИЕ СЛОЖНОСТИ МЕТОДОВ

Приведем сравнительный анализ оценок (7), (14) и (23), соответствующих сложности методов ТМ, СМ и УО.

Сравнивая (7) и (14) видно, что рост времени выполнения при росте точности одинаков для обоих методов, в то время как рост времени выполнения при росте размерности существенно хуже у метода СМ. Этот результат не случаен: так, в [8], теорема 4, получена оценка для величины $\mathop {\lim }\limits_{\varepsilon \to 0} \left( {{{{{k}_{{{\text{Sph}}}}}(d,\varepsilon )} \mathord{\left/ {\vphantom {{{{k}_{{{\text{Sph}}}}}(d,\varepsilon )} {{{k}_{{{\text{opt}}}}}(d,\varepsilon )}}} \right. \kern-0em} {{{k}_{{{\text{opt}}}}}(d,\varepsilon )}}} \right)$, которая является вариантом асимптотической эффективности. Из оценки видно, что при больших d указанная величина стремится к нулю со скоростью Θ(d d), что говорит о крайней неэффективности использования сферических координат для покрытия сферы при больших d.

Сравнивая оценку (23) с оценками (7) и (14), заметим, что рост времени выполнения от точности существенно медленнее в (23). В то же время при фиксированной точности и росте размерности оценка (23) значительно хуже (7) и лучше (14). Это происходит, главным образом, за счет того, что прирост числа граней аппроксимирующего многогранника в методе УО не зависит от точности, но экспоненциально зависит от размерности. Эта особенность метода УО была также обнаружена в экспериментальных исследованиях, описание которых выходит за рамки данной статьи, при аппроксимации шаров размерностей от 3 до 10.

7. ЗАКЛЮЧЕНИЕ

В статье исследована проблема построения аппроксимации многомерного шара многогранниками двойного описания. Выделены два подхода к решению этой задачи: последовательный и прогрессивный. Сформулированы и изучены три метода аппроксимации многомерного единичного шара многогранниками двойного описания.

Первые два метода: ТМ и СМ представляют реализацию последовательного подхода. Метод ТМ – теоретический – основан на асимптотически оптимальных последовательностях вершин аппроксимации ВКТ. Этот метод не предлагает конструктивного способа аппроксимирующих многогранников, но позволяет получить асимптотическую оценку зависимости сложности аппроксимации от точности аппроксимации и размерности шара, которая, вообще говоря, не может быть улучшена в классе методов, реализующих последовательный подход. Метод СМ заключается в использовании простой неадаптивной сетки точек на поверхности аппроксимируемого тела, основанной на сферических координатах. Такой метод часто используется в приложениях. В статье показано, что этот метод достаточно неэффективен, в сравнении с двумя другими исследованными методами, с точки зрения роста его сложности как с ростом точности аппроксимации, так и с ростом размерности аппроксимируемого шара.

Наконец, метод УО, представляющий прогрессивный подход к аппроксимации ВКТ многогранниками двойного описания, в сравнении с теоретическим последовательным методом, оказался эффективнее как с точки зрения роста сложности с ростом точности аппроксимации, так и с точки зрения роста сложности с ростом размерности аппроксимируемого шара.

В качестве практической рекомендации, при прочих равных условиях, можно предложить при аппроксимации ВКТ многогранниками двойного описания использовать прогрессивный подход, в частности метод УО. За рамками статьи оказалось исследование влияния сложности внешнего, по отношению к методу аппроксимации ВКТ многогранниками двойного описания, оптимизационного модуля расчета опорной функции ВКТ на сложность всего метода аппроксимации ВКТ, поскольку в изученном случае аппроксимации гипершара расчет опорной функции тривиален. В [33] обсуждается вопрос использования распределенных вычислений при полиэдральной аппроксимации одного класса выпуклых тел, и делается вывод, что, в определенных условиях, могут оказаться предпочтительнее методы построения многогранника двойного описания, основанные на субоптимальном покрытии многомерной сферы.

Список литературы

  1. Motzkin T.S., Raiffa H., Thompson G.L., Trall R.M. The Double Description Method // Contributions to the Theory of Games. 1953. V. 2. P. 51–73.

  2. Лотов А.В., Бушенков В.А., Каменев Г.К. Метод достижимых целей. Математические основы и экологические приложения. NY USA: The Edwin Mellen Press, 1999. 400 с.

  3. Бронштейн Е.М. Аппроксимация выпуклых множеств многогранниками // Современная математика. Фундаментальные направления. 2007. Т. 22. С. 5–37.

  4. Schneider R. Zur optimalen Approximation konvexer Hyperflächen durch Polyeder // Math. Ann. 1983. P. 289–301.

  5. Schneider R. Polyhedral approximation of smooth convex bodies // J. Math. Analys. and Applic. 1987. V. 128. № 2. P. 470–474.

  6. Каменев Г.К., Лотов А.В., Майская Т.С. Итеративный метод построения покрытий // Ж. вычисл. матем. и матем. физ. Т. 53. № 2. 2013. С. 181–194.

  7. Каменев Г.К., Лотов А.В., Майская Т.С. Построение субоптимальных покрытий многомерной единичной сферы // Докл. АН. 2012. V. 444. № 2. P. 153–155.

  8. Майская Т.С. Оценка радиуса покрытия многомерной единичной сферы метрической сетью, порожденной сферической системой координат // Сб. cтатей молодых ученых факультета ВМК МГУ. 2011. № 8. С. 83–98.

  9. Avis D., Bremner D., Seidel R. How good are convex hull algorithms? // Comput. Geometry. 1997. V. 7. № 5–6. P. 265–301.

  10. Fourier J.B. Solution d’une question particuliere du calcul des inegalites // In: Nouveau bulletin des sciences par la societe philomatique de Paris. 1826.

  11. Burger E. Uber homogene lineare Ungleichungssysteme // Zeitschrift fuer Angewandte Math. und Mech. 1956. V. 36. № 3/4.

  12. Черников С.Н. Линейные неравенства. М.: Наука, 1966. 488 с.

  13. Fukuda K., Prodon A. Double description method revisited // In: Combinatorics and Computer Science. Volume 1120 of the series Lecture Notes in Computer Science. 1996. P. 91–111.

  14. Бушенков В.А., Лотов А.В. Алгоритм анализа независимости неравенств линейной системы // Ж. вычисл. матем. и матем. физ. 1980. Т. 20. № 3.

  15. Бушенков В.А., Лотов А.В. Методы и алгоритмы анализа линейных систем на основе построения обобщенных множеств достижимости // Ж. вычисл. матем. и матем. физ. 1980. Т. 20. № 5.

  16. Черных О.Л. Построение выпуклой оболочки множества точек в виде системы линейных неравенств // Ж. вычисл. матем. и матем. физ. 1992. V. 32. № 8. P. 1213–1228.

  17. Seidel R. A convex hull algorithm optimal for point sets in even dimensions, 1981.

  18. Препарата Ф., Шеймос М. Вычислительная геометрия. Введение. М.: Мир, 1989.

  19. Barber C.B., Dobkin D.P., Huhdanpaa H. The Quickhull Algorithm for Convex Hulls // ACM Transactions on Mathematical Software. 1996. V. 22. № 4. P. 469–483.

  20. Chand D., Kapur S. An algorithm for convex polytopes // J. ACM. 1970. V. 17. P. 78–86.

  21. Chazelle B. An optimal convex hull algorithm in any fixed dimension // Discrete Comput. Geom. 1993. № 10. P. 377–409.

  22. Бушенков В.А., Лотов А.В. Методы построения и использования обобщенных множеств достижимости. М.: ВЦ РАН, 1982.

  23. Каменев Г.К. Об одном классе адаптивных алгоритмов аппроксимации выпуклых тел многогранниками // Ж. вычисл. матем. и матем. физ. 1992. Т. 32. № 1. С. 136–152.

  24. Каменев Г.К. Методы аппроксимации выпуклых тел многогранниками и их применение для построения и анализа обобщенных множеств достижимости. Дис. ... канд. физ. матем. наук. М.: МФТИ, 1986.

  25. Лотов А.В. Методы анализа математических моделей управляемых систем на основе построения множества достижимых значений показателей качества управления. Дис. … докт. физ. матем. наук. М.: МФТИ, 1985.

  26. Каменев Г.К. Исследование одного алгоритма аппроксимации выпуклых тел // Ж. вычисл. матем. и матем. физ. 1994. Т. 34. № 4. С. 608–616.

  27. Ефремов Р.В., Каменев Г.К. Об оптимальном порядке роста числа вершин и гиперграней в классе хаусдорфовых методов полиэдральной аппроксимации выпуклых тел // Ж. вычисл. матем. и матем. физ. 2011. Т. 51. № 6. С. 1018–1031.

  28. Каменев Г.К. Метод полиэдральной аппроксимации шара с оптимальным порядком роста мощности гранной структуры // Ж. вычисл. матем. и матем. физ. 2014. V. 54. № 8. P. 1235–1248.

  29. Каменев Г.К. Асимптотические свойства метода уточнения оценок при аппроксимации многомерных шаров многогранниками. 2015. Т. 55. № 10. С. 1647–1660.

  30. Абрамов С.А. Лекции о сложности алгоритмов. МЦНМО, 2009.

  31. Gruber P.M. Approximation of convex bodies // In: Convexity and its Applics. 1983. P. 131–162.

  32. Роджерс К. Укладки и покрытия. М.: Мир, 1968.

  33. Лотов А.В., Майская Т.С. Неадаптивные методы полиэдральной аппроксимации оболочки Эджворта–Парето, использующие субоптимальные метрические сети на сфере направлений // Ж. вычисл. матем. и матем. физ. 2012. V. 52. № 1. P. 35–47.

  34. Половинкин Е.С., Балашов М.В. Элементы выпуклого и сильно выпуклого анализа. М.: Физматлит, 2004. 416 p.

  35. Торп Д. Начальные главы дифференциальной геометрии. Платон, 1982.

  36. Avis D., Fukuda K. A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra // Discrete Comput. Geom. 1992. V. 8. № 3. P. 295–313.

  37. Bremner D., Fukuda K., Marzetta A. Primal–dual methods for vertex and facet enumeration // Discrete Comput. Geom. 1998. № 20. P. 333–357.

  38. Khachiyan L., Boros E., Borys K., Elbassioni K., Gurvich V. Generating all vertices of a polyhedron is hard // Discrete Comput. Geom. 2008. № 39. P. 174–190.

  39. Bremner D.D. On the complexity of vertex and facet enumerationx for convex polytopes. Montreal: School of Computer Science, McGill University, 1997.

Дополнительные материалы отсутствуют.

Инструменты

предыдущая статья выпуска содержание выпуска

Журнал вычислительной математики и математической физики

Архивы выпусков Информация о журнале Отправить рукопись в журнал