Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
procedure СПУСК(и.р) begin if(w ф лист) then
begin(QL, <Ы:=РАСЦЕПИТЬ(С/[»]; J[v])
С/[ЛСЫН[о]] := СЦЕПИТЬ^,ф[ЛСЫНМ]); ?/[ПСЫН[о]] := СЦЕПИТЬ(<2[ПСЫНМ],<2я); if [х\р] < x[v]) then v := ЛСЫН[и] else v := ПСЫН[о]; СПУСК(о.р)
end
end.
Здесь мы вставляем новый лист и начинаем двигаться по тому же самому пути в Г к корню дерева. При достижении каждого узла v, лежащего на этом пути, у нас имеется полная В-оболочка, относящаяся к этому узлу. Как уже было показано, в узле v доступна также В-оболочка брата узла v. Так что теперь мы соединяем эти две оболочки, используя эффективное расцепление В-оболочки U [v] на две части Qi и Q2 и соответственно ?/[БРАТ[и]] на Q3 и Q4. Части Q2 и Q3 должны сохраняться в узлах v и БРАТ[у] соответственно, в то время как часть Qi должна быть передана в узел, являющийся отцом узла v, где она будет сцеплена с аналогичной частью Q4, полученной от брата узла v. Таким образом мы получили В-оболочку узла, являющегося отцом узла v, и подъем к корню дерева может быть продолжен. И вновь, если говорить более формально, мы используем следующую процедуру:
3.4. Выпуклые оболоч
размерности большей двух
159
begii
procedure ПОДЪЕМ(я) igin if(u ф корень) then
begin(Q,,Q2,Q3,Q4, J):= СОЕДИНИТЬ(?/[о],
end;
else Q[v] := U[v]
end.
Рассматривая эти процедуры с точки зрения времени их выполнения, напомним, что каждая из процедур РАСЦЕПИТЬ и СЦЕПИТЬ выполняется за время О (log k), где k — размер очереди до расцепления или после сцепления. Так как k^N, то видно, что время обработки одного узла в процедуре СПУСК составляет О (log N). А так как глубина дерева Т также равна O(logjV), то время выполнения процедуры СПУСК равно О (log2 iV) в худшем случае. Что касается процедуры ПОДЪЕМ, то, как мы видели ранее, время выполнения процедуры СОЕДИНИТЬ также равно О (log Л7), и поэтому та же оценка применима и в этом случае. Аналогичный анализ времени выполнения можно использовать и в случае удаления точки из текущего множества, и мы оставляем его в качестве упражнения для читателя. Таким образом, можно подвести итоги этого раздела, сформулировав следующую теорему:
Теорема 3.12. Динамическая поддержка В-оболочки и Н-обо-лочки множества из N точек на плоскости может быть выполнена с временными затратами на операции вставки и удаления, равными О (log2 N) в худшем случае.
Заметим, что если пользоваться этим методом для построения выпуклой оболочки множества из N точек в случае, когда допускается только добавление точек, то получим оценку для времени выполнения 0(N log2 N), более высокую по сравнению с О (Л7 log Л7) для менее «мощного» метода. Ясно, что это является платой за использование метода, более мощного, чем требуется в конкретной задаче.
3.4. Выпуклые оболочки в пространствах размерности большей двух
Теперь мы готовы к тому, чтобы рассмотреть задачу построения выпуклой оболочки конечного множества точек в пространствах размерности большей двух. Мы уже видели, что
160
Гл. 3. Выпуклые оболочки: основные алгоритмы
такая оболочка является выпуклым политопом. Мы также видели, что политопы в случае большого числа измерений уже не являются такими простыми геометрическими объектами, как их двумерные аналоги — выпуклые многоугольники. Однако напомним, что в трехмерном пространстве число вершин v, число ребер е и число граней f границы оболочки (многогранной поверхности) связаны формулой Эйлера v — е -f- f = 2.
В случае пространств высокой размерности удобно использовать следующие понятия. Будем говорить, что точка р находится под гипергранью F политопа Р, если р лежит в открытом
Рис. 3.24. Иллюстрация понятий «под» и «над» в двумерном случае.
полупространстве, определяемом гиперплоскостью atl(F) и содержащем Р. (Другими словами, aff (Р) является опорной гиперплоскостью к Р, а р и Р принадлежат одному и тому же полупространству, ограничиваемому этой гиперплоскостью.) Точка р находится над F, если р лежит в открытом полупространстве, определяемом aff(P) и не содержащем Р. Рис. 3.24 иллюстрирует эти понятия в двумерном случае.
3.4.1. Метод «заворачивания подарка»
Как упоминалось ранее (разд. 3.1.2), неизвестны разумно эффективные алгоритмы построения выпуклой оболочки конечного множества точек, которые не порождали бы полного описания границы (граф граней) выпуклой оболочки политопа. Поэтому в случае с(-мерного пространства необходимо тщательно организовывать процедуру вычисления гиперграней выпуклой оболочки, чтобы ограничить возможные дополнительные затраты. Важным шагом в этом направлении является метод «заворачивания подарка», предложенный Чандом и Капуром (Chand, Kapur (1970)]. Этот метод был проанализирован более чем десятилетие спустя Бхаттачарья [Bhattacharya (1982)].
3.4. Выпуклые оболочки размерности большей двух
161
Основная идея метода заключается в последовательном переходе от одной гиперграни к смежной с ней гиперграни примерно так, как это происходит при заворачивании в лист бумаги объекта, ограниченного плоскими гранями. Простейшим примером этого подхода является метод обхода Джарвиса, обсуждавшийся ранее (разд. 3.3.3): в этом случае материал, используемый для заворачивания, больше похож на тесемку, чем на лист бумаги. Идея метода более естественно воспринимается в трехмерном пространстве, и мы часто будем обращаться именно к этому случаю, чтобы привлечь интуицию читателя. Однако необходимо подчеркнуть, что обсуждение на примере трехмерного пространства обусловлено причинами, связанными чисто с представлением материала, и при этом нисколько не ограничивается общность рассматриваемого подхода. Последующее обсуждение основано на предположении о том, что результирующий политоп является симплициальным (см. разд. 3.1). Позже мы прокомментируем ситуацию в общем случае.
