Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Структура данных, используемая при проверке приемлемости ребер, является динамической, так как она должна изменяться (перестраиваться) каждый раз, как некоторое ребро включается в триангуляцию. Учитывая, однако, что в каждой звезде изменения затрагивают множество последовательных секторов, вполне естественно использовать деревья отрезков (см. разд. 1.2.3.1). В частности, секторы, порождаемые ЗВЕЗДА (pi), представлены (Л/—1) листьями дерева отрезков Ti. С каждым узлом v дерева Ti связано ребро e(v), являющееся ближайшим ребром к pi среди всех ребер, которые связывались с узлом v в результате вставки в дерево отрезков. (Очевидно, что e(v) может быть пустым ребром.) При проверке ребра piPj выполняется поиск в дереве Г,-, осуществляемый с помощью прохождения пути, определяемого р,-. В каждом узле v, лежащем на этом пути, производится проверка взаимного положения точки pj и ребра e(v). Ребро считается допустимым тогда и только тогда, когда оно не пересекает ни одно из ребер, встретившихся при прохождении пути. Если выбранное ребро оказывается непригодным, то поиск прекращается. Иначе, когда ребро р,р; является допустимым, необходимо произвести изменения: перестроить деревья, соответствующие каждому из множеств ЗВЕЗДА (р/), где 1ф1, j. Это реализуется просто путем вставки ребра р*р/ в дерево для ЗВЕЗДА (pi) и надлежащего изменения каждого узла v, лежащего на путях, проходимых при вставке. (Отсылаем читателя к разд. 1.2.3, где подробно рассмотрена работа с деревьями отрезков.) Очевидно, что изменения в каждом из деревьев, соответствующих ЗВЕЗДА (pi), 1=1, N, можно сделать за время 0(\ogN). Так как, если некоторое ребро оказывается допустимым, необходимо произвести изменения в (N — 2) деревьях и эта операция выполняется O(N) раз, то полное время, необходимое на выполнение изменений в деревьях при триангуляции, составляет 0(N2logN).
Учитывая, что на управление выбором ребер, проверку допустимости ребер и внесение изменений в структуры данных требуется время 0(N2\ogN) (на каждую в отдельности), получаем следующий результат:
10 Зак. 1075
290 Гл. 6. Близость: варианты и обобщения
Теорема 6.4. Триангуляция множества из N точек жадным методом может быть выполнена за время 0(N2\ogN) с использованием памяти объемом О (N2).
6.2.2. Триангуляция с ограничениями
Во многих случаях природа решаемой задачи такова, что при триангуляции необходимо учитывать разного рода ограничения, т. е. в исходной постановке задачи на множество ребер триангуляции накладываются некоторые ограничения. Типичный пример такой ситуации дает задача триангуляции внутренности простого многоугольника.
Из всех описанных ранее методов для решения таких задач с ограничениями можно было бы использовать жадный метод, но он имеет один недостаток: 'эффективность получения решения далека от оптимальной. С другой стороны, не видно способа приспособить для решения таких задач метод триангуляции Делоне. (См. разд. 5.6 и 6.5.) Следовательно, необходимо искать новый метод.
Как обычно, на плоскости задано множество S из N точек. Кроме того, на 5 задано множество Е из М непересекающихся ребер (ограничения), которые должны войти в число ребер триангуляции. Мы немного и несущественно изменим предыдущее соглашение, условившись, что область, подвергаемая триангуляции, представляет наименьший прямоугольник rect(S), стороны которого параллельны координатным осям, охватывающий все точки множества S. (Заметим, что в rect(S) существуют по крайней мере две вершины, имеющие наибольшее значение у-координаты, и по крайней мере две вершины с наи- I меньшей (/-координатой.)
Цель состоит в том, чтобы эффективно выполнить разбиение rect(S) на многоугольники меньшего размера, триангуляция которых не вызывает затруднений. Следующее определение описывает класс таких многоугольников [Garey, Johnson, Preparata, Tarjan (1978)].
Определение 6.1. Многоугольник Р называется монотонным . относительно прямой /, если он простой и его граница является ( объединением двух цепей, монотонных относительно / (см. разд. 2.2.2.2.)')•
Будем предполагать далее, что прямая / — это у = 0 системы координат и что никакие две точки множества 5 не ( имеют одинаковую ординату (как обычно, это предположение
') Было показано, что проверка монотонности простого многоугольника может быть выполнена за линейное время [Preparata, Supowit (1981)].
6.2. Планарные триангуляции
291
не принципиально, но упрощает рассмотрение). Далее будет представлен простой алгоритм триангуляции монотонного многоугольника, а сейчас покажем, как можно выполнить разбиение прямоугольника rect(S).
Предлагаемый метод принадлежит классу методов, основанных на заметании плоскости, и, по существу, совпадает с процедурой «регуляризации» планарного графа, описанной в разд. 2.2.2.2. Действительно, множества S и Е определяют пленарный граф, уложенный на плоскости. Процедура регуляризации (описание которой здесь не приводится, чтобы не делать ненужных повторений) за время O(NlogN) добавляет ребра так, что выполняются следующие условия:
