Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Теперь можно оценить полную сложность алгоритма. Сложность начального этапа работы алгоритма (шаги 1—4) составляет 0(Nd2). Шаги 6, 11 и 12 (добавление в очередь и удаление из очереди или вывод гиперграни) можно рассматривать совместно. Если обозначить через <ра-\ и ф<*_2 действительные числа соответственно гиперграней и подграней политопа, то их полная сложность равна 0(с?)Хф<*-1. Полная сложность шага 7 — порождение всех подграней — равна О (d) X ф<*-2, так как каждая подгрань строится за время 0(d) и порождается дважды. Проверка, выполняемая на шаге 8, так же как и изменение файла на шаге 10, выполняется за время 0(eMog<pd_2) на каждую подгрань, так что полная сложность составляет 0(d log ф<*-2) X <P<i-2- Наконец, полная сложность шага 9 — шаг заворачивания — равна ф<*-1Х(0(^3) + O(Nd)). Если вспомнить, что максимальное значение как для ф<*-ь так и для ф<*_2 равно О (yvLd/2J), то получим следующий результат:
Теорема 3.14. Выпуклая оболочка множества из N точек в d-мерном пространстве может быть построена методом «заворачивания подарка» за время T(d, N) = 0(N-<fd-i) + 0(ф<*-гХ Х^фй-г). Таким образом, в худшем случае имеем T(d, N) = = 0(yVu'2J+1) + 0(^/2JlogA7).
В заключение отметим, что нельзя игнорировать тот факт, что рассмотренный выше метод применим в предположении
1 SF(rf, N) =01)(wLd/2J)[Grunbaum (1967), 9.6.11.
3.4. Выпуклые оболочки размерности большей двух 167
симплициальности результирующего политопа. Что происходит в общем, хотя практически невероятном случае, когда гиперграни содержат более d вершин? Если гипергрань F не является симплексом, то уравнение (3.10) имеет более одного решения, т. е. в множестве 5 имеются несколько точек, реализующих это условие. Все эти точки принадлежат гиперплоскости ati(F). Однако для того, чтобы определить состав граней, входящих в F (т.е. (d — 2)-грани, 0-грани), необходимо в свою очередь (рекурсивно) решать (d — 1)-мерную задачу построения выпуклой оболочки в aff(f). Таким образом, процедура порождения подграней, не вызывавшая затруднений в случае симплициаль-ного политопа, становится значительно более сложной. А рекурсивное определение алгоритма для общего случая, естественно, существенно затрудняет его анализ.
3.4.2. Метод «под-над»
В течение длительного времени метод «заворачивания подарка» оставался единственным из известных общих методов построения выпуклой оболочки конечного множества точек в rf-мерном пространстве. Новый метод, названный «под-над», был предложен Кейли [Kallay (1981)]. Этот алгоритм обладает также свойством открытости.
Основная идея метода существенно отличается от используемой в методе «заворачивания подарка» и довольно близка идее, используемой в алгоритме для динамической двумерной выпуклой оболочки, описанном в разд. 3.3.6. На содержательном уровне этот метод последовательно обрабатывает по одной точке, назовем ее р, и если р — внешняя точка по отношению к текущей оболочке Р, то из точки р строится опорный «конус» к Р и удаляется часть оболочки Р, затеняемая этим конусом. (Использование терминов «конус» и «затенение» происходит по аналогии с трехмерным случаем.) Рассматриваемый метод основан на следующей теореме [McMullen, Shephard (1971), p. 113]:
Теорема 3.15. Пусть Р —политоп, а р — точка в пространстве Ed. Введем обозначение Р' = СН(Р U р). Тогда для каждой грани Р' справедливо одно из двух утверждений:
(1) грань f политопа Р является также гранью Р' тогда и только тогда, когда существует гипергрань F политопа Р такая, что f cz F и р находится под F;
(2) если f — грань политопа Р, то f' = CH(/Up) является гранью Р' тогда и только тогда, когда либо
(а) среди гиперграней политопа Р, содержащих f, имеется по крайней мере одна такая, что р находится под ней, и по крайней мере одна такая, что р находится над ней, либо
(b)peaff(f).
168
Гл. 3. Выпуклые оболочки: основные алгоритмы
Интуитивно понятно, что случай (1) относится к гиперграням политопа Р, незатеняемым конусом и которые становятся гипергранями Р', представляющего измененную выпуклую оболочку. (См. рис. 3.27, на котором показаны все случаи на примере простого, но вместе с тем не теряющего общности двумерного пространства.) Случай (2) относится к гиперграням конуса. В частности, пункт (а) случая (2) определяет грани, на которые опирается конус, а пункт (Ь) определяет вырожденный
Рис. 3.27. Иллюстрация случаев, рассматриваемых в теореме 3.15.
вариант ситуации, определяемой в пункте (а). Заметим, что в п. (а) случая (2), размерность грани f = СН(/ U р) оболочки Р' на единицу больше размерности грани f политопа Р. И хотя в общем случае целью является построение лишь гиперграней выпуклой оболочки, эффект увеличения размерности, имеющий место в п. (а) случая (2), вынуждает иметь необходимое описание всех граней текущего политопа.
Так как алгоритм является открытым, т. е. выпуклая оболочка строится путем последовательного добавления по одной точке, то потребуется по крайней мере (cf+l) итераций, прежде чем текущий политоп будет иметь размерность d. Это значит, что сначала получается 0-грань, затем 1-грань и т. д. Однако механизм перестройки выпуклой оболочки остается тем же самым, и далее он будет описан в общем случае. Для простоты предполагается, что точки находятся в общем положении, так что вырождение не имеет места.
