Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
172
Гл. 3. Выпуклые оболочки: основные алгоритмы
Теорема 3.16. Выпуклая оболочка множества из N точек в d-мерном пространстве может быть построена методом «под-над», являющимся открытым, за время T(d, N) — 0 (NLdl2A+x).
Сделаем два замечания. Первое, в рассмотренном методе необходимо предусмотреть специальную обработку вырожденных случаев, когда точка р принадлежит аффинной оболочке некоторой грани политопа Р. Второе, можно показать, что в случае, когда политоп Р не является симплициальным, можно слегка изменить Р, не увеличив существенным образом сложность структуры его граней или сложность отношения включения. И как следствие, временная оценка, полученная для симплици-ального случая, остается применимой и в общем случае.
В заключение отметим, что метод «под-над» весьма привлекателен, так как его сложность сравнима со сложностью метода «заворачивания подарка» и, кроме того, он является открытым, что тоже очень важно.
3.4.3. Выпуклые оболочки в трехмерном пространстве
Для задачи построения выпуклой оболочки в многомерных пространствах случай трехмерного пространства имеет огромную важность, так как он естественным образом возникает во множестве прикладных областей, включающих машинную графику, автоматизацию проектирования, распознавание образов, исследование операций. К счастью, этот важный для приложений случай одновременно является «изюминкой» с точки зрения сложности вычислений. Далее мы попытаемся пояснить эту несколько туманную мысль.
Как уже отмечалось ранее, результатом работы алгоритмов построения выпуклой оболочки должно быть описание политопа, представляющего выпуклую оболочку. Из разд. 3.1 известно, что тривиальная нижняя оценка сложности в худшем случае для любого алгоритма построения выпуклой оболочки N точек в пространстве Ed, основанная на размере результирующего описания, равна Q (jVu/2J). В предыдущем разделе было показано также, что оценка для метода «под-над» превышает эту нижнюю оценку на множитель O(N), и для d = 3 (d в этом случае нечетное число) это лучшее, что можно ожидать для открытого метода. Если отказаться от свойства открытости, то можно рассчитывать, что удастся уменьшить этот множитель, получив вместо O(N) что-нибудь, подобное O(logAf). В трехмерном случае это дало бы оценку О (NL3,2J log N) = О (N log N) С другой стороны, нижняя оценка в общем случае в точности равна Q(N log N) (см. разд. 3.2), поэтому лучшее, на что можно
3.4. Выпуклые оболочки размерности большей двух
173
надеяться, это получить алгоритм со сложностью G(iVlogiV). И эта цель достижима (Preparata, Hong (1977)].
Как обычно, пусть имеется множество 5 = {ри р2, .. ., Pn) из N точек в пространстве Е3. Для простоты предположим, что для любой пары точек р, и р,- из S имеет место хи {pi) Ф xk (р/), k = 1, 2, 3. Это упрощение поможет яснее показать основные идеи алгоритма, а изменения, которые необходимо сделать в алгоритме для общего случая, очевидны. Здесь мы попытаемся разработать алгоритм типа «разделяй и властвуй» со сложностью 0(N log N).
Для начала упорядочим множество S по координате Х\ и, если это необходимо, перенумеруем точки так, чтобы *i(p,-)< < х{ (ру) <=>- i </. Существует следующий простой рекурсивный алгоритм построения выпуклой оболочки (представленный в виде функции):
function CH(S) 1. begin if (|S|<ft0) then
begin построить CH(S) методом "грубой силы"; return CH(S)
end
else begin S,
S2
end.
end
= {pu ¦ • - , PLA72j};
= {Pl,v/2J+i> • • •' Pn}'' = CH(5i); P2:=CH(S2); = СЛИТЬ(Р,,Р2); return P
Предварительная сортировка элементов множества S по координате Х\ требует О (N log N) операций. Отметим, что благодаря такой сортировке и тому, как выполняется шаг 2 алгоритма, множества CH(Si) и СН(52) представляют два непересекающихся трехмерных политопа. Если «слияние», т. е. построение выпуклой оболочки объединения двух выпуклых оболочек с суммарным числом вершин, равным N, может быть выполнено не более чем за M(N) операций, то верхняя оценка для T(N)~ числа операций, выполняемых алгоритмом СН, определяется уравнением T(N) = 2Т (N/2)М (N). (Отметим, что для простоты мы считаем N четным, но это не влияет на общность результата.) Таким образом, если мы сумеем показать, что M(N) равно O(N), то получим для T(N) оценку O(NlogN) и, учитывая затраты на предварительную сортировку, получим оценку 0(N\ogN) для сложности всего алгоритма построения выпуклой оболочки.
Ясно, что функция СЛИТЬ является критическим местом рассматриваемого метода. Начнем с обсуждения структуры дан-
174
Гл. 3. Выпуклые оболочки: основные алгоритмы
ных, подходящей для представления выпуклого трехмерного политопа Р. Необходимо описать лишь границу политопа Р, которая в трехмерном случае топологически эквивалентна плоскому графу. Как отмечалось в разд. 1.2.3.2, естественной структурой для представления плоского графа является рёберный список с двойными связями (РСДС). РСДС обладает интересным свойством — явным образом он содержит только ребра графа, но эта структура позволяет за оптимальное время выделять вершины и множества вершин граней1).
