Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Следующее соображение связано с большим количеством сравнений углов, каждое из которых должно выполняться за постоянное время путем адаптации общего метода, описанного
продвиж
при построении Т.
3.4. Выпуклые оболочки размерности большей двух
177
в разд. 3.4.1 для случая d-мерного пространства. В результате сравнения типа 1 из дальнейшего рассмотрения обязательно исключается одно ребро, принадлежащее либо Pi, либо Р2. Пусть Vi и trii обозначают соответственно число вершин и число ребер Pi (i = 1, 2). Таким образом, число сравнений типа 1 ограничено сверху величиной (mj + m2). Далее каждое сравнение типа 2 добавляет новую вершину либо к Еи либо к Е2. Так как число вершин в контурах Ех и Е2 не может превышать соответственно v\ и v2, то число сравнений типа 2 ограничено величиной (vi -j- v2— 1). Поскольку граф, представляющий структуру поверхности политопа, является планарным, nii ^ Зи; — 6, и, следовательно, число сравнений углов растет не быстрее линейной функции от суммарного числа вершин политопов Рх и Р2.
Корректировку РСДС можно производить динамически в процессе построения ST. Воспользуемся иллюстрацией на рис. 3.31. Предположим, мы продвинулись от ребра (а, Ь{) к ребру (а, Ь), «поворачиваясь» вокруг вершины а. Произойдет просмотр ребер, инцидентных как вершине Ь, так и вершине а, хотя ребра, инцидентные а, уже были частично просмотрены ранее. Сначала в РСДС создается новый узел для ребра (а, Ь) и ребро (а, Ь) становится следующим за (а, Ьх) вокруг а, а (b\, Ь) становится следующим за ним вокруг Ь\. Теперь начинается просмотр ребер, инцидентных Ь, в порядке движения по часовой стрелке вокруг Ь, начиная с ребра в\ и кончая ее узлы, соответствующие ребрам е2 и ез, были удалены ]) (так как е2 и е3 оказались внутри оболочки), а ребро (а, Ь) становится следующим за ребром е\. Аналогичный просмотр осуществляется вокруг вершины а, начиная с некоторого ребра е'Л до некоторого другого ребра е' = (а, а5). Затем, если в результате сравнения углов выбирается гипергрань (a, b, Ь4), то ребра (a, bt) и (b, bt,) становятся следующими за ребром (а, Ь) вокруг вершин а и b соответственно. В противном случае вместо них берутся (а, а5) и (Ь, а5). Это приводит к корректировке РСДС как связанной структуры данных. Отсюда следует, что полное время, требуемое алгоритму СЛИТЬ, равно O(N), и поэтому имеет место следующая теорема.
Теорема 3.17. Выпуклая оболочка множества из N точек в трехмерном пространстве может быть построена за оптимальное время 6 (N log N).
') Заметим, что при такой процедуре удаления ребер из РСДС не все ребра, попавшие внутрь выпуклой оболочки, могут быть удалены. Однако неудаленные (таким образом) ребра образуют планарный граф с множе^-ством вершин V, которые сами являются внутренними точками выпуклой оболочки. Поэтому, число неудаленных ребер пропорционально \ V'\, и полный объем памяти, занимаемой РСДС, остается пропорциональным |S|. Отметим, что граф с множеством вершин V не связан с графом выпуклой оболочки.
178
Гл. 3. Выпуклые оболочки: основные алгоритмы
В заключение необходимо обсудить, как быть с вырожденными ситуациями, когда политопы не является симплициальны-ми. Самое разумное решение основывается на введении «искусственной» триангуляции гиперграней, не являющихся треугольниками, и тогда политоп все время остается симплициальным. Рассмотрим, в частности, процедуру просмотра множества ребер, инцидентных вершине Ь (рис. 3.32). В предположении симплициальности политопа просмотр завершается на ребре е, принадлежащем двум гиперграням F и F', так что при этом вершина а находится над F и под F' (относительно смысла терминов «над» и «под» см. начало разд. 3.4). Это единственно возможная ситуация, так как в соответствии с предположением никакие четыре точки не могут лежать в одной плоскости. При отказе от этого предположения критерий завершения просмотра ребер становится следующим: просмотр Рис. 3.32. Пример триангуляции ги- заканчивается на ребре е, при-перграни, не являющейся треуголь- надлежащем гиперграням F и ником- F' таким, что вершина а нахо-
дится не под F и над F'. В таком случае, если вершина а и гипергрань F принадлежат одной гиперплоскости, то результирующая гипергрань QH(F\}a) оказывается разбитой на треугольники пучком ребер, выходящих из вершины а (рис. 3.32). Таким образом, грани &~ будут треугольниками, хотя смежные гиперграни могут лежать в одной гиперплоскости. Лишние ребра легко могут быть удалены за один проход по РСДС по окончании построения выпуклой оболочки. При прохождении РСДС отмечается каждое ребро, компланарное с двумя своими соседями, инцидентными одной и той же вершине, а затем все отмеченные ребра удаляются.
3 5, Замечания и комментарии
В этой главе мы неоднократно указывали на тесную связь задач сортировки и построения выпуклой оболочки на плоскости. В частности, любой алгоритм, строящий упорядоченную последовательность вершин выпуклой оболочки, т. е. решающий задачу В01 в случае плоскости независимо от реализуемого им метода, является замаскированным алгоритмом
