Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Отсылаем читателя к разд. 5.6, где подробно рассмотрены свойства триангуляции Делоне. Далее будут рассмотрены некоторые другие методы триангуляции применительно либо к множествам точек, либо к смешанным множествам, содержащим точки и отрезки. Здесь стоит напомнить, что для построения триангуляции множества из ./V точек на плоскости любым из алгоритмов требуется Q(N\ogN) операций (см. разд. 5.3).
6.2.1. Жадная триангуляция
Как хорошо известно, «жадный» метод — это такой метод, при котором никогда не отменяется то, что уже было сделано ранее. Таким образом, жадный метод триангуляции последовательно порождает ребра триангуляции (по одному за раз) и завершает этот процесс после того, как порождено не-
') Однако известно, что минимальная взвешенная триангуляция индивидуального iV-угольника может быть вычислена за время 0{N3) [Gilbert
6.2. Планарные триангуляции
287
обходимое число ребер, которое полностью определяется размером множества точек и его выпуклой оболочкой. Если цель состоит в минимизации суммарной длины ребер, то все, что можно сделать, используя жадный метод, это применить локальный критерий, добавляя на каждом этапе кратчайшее из возможных ребер, совместимое с ранее порожденными ребрами, т. е. не пересекающее ни одно из них.
В этом суть метода. Непосредственная реализация этой идеи сводится к следующей последовательности действий (как обычно, 5 обозначает множество точек, а N — его размер). Сначала
няющих точки множества S, которые затем упорядочиваются по возрастанию длин, образуя пул ребер. Вначале множество ребер триангуляции является пустым. Основной шаг процедуры триангуляции включает следующие действия. В пуле выбирается и исключается из него ребро наименьшей длины. Если это ребро не пересекает ни одно из ребер, уже вошедших в триангуляцию, то оно также включается в число ребер триангуляции. Иначе ребро просто исключается из дальнейшего рассмотрения. Процесс завершится, либо когда будет построена триангуляция (что можно определить, подсчитывая число добавляемых ребер), либо когда пул ребер станет пустым [Duppe, Gottschalk (1970)].
Этот метод, рассмотренный здесь лишь в общих чертах, прост не только для реализации, но и для анализа. Для сортировки ребер по длине требуется 0(N2logN) операций. За-
выбранное ребро проходит проверку на пересечение с ребрами, уже вошедшими в триангуляцию, на что требуется некоторое время ф (Л/). Вид ф зависит от метода, реализующего эту проверку. В результате получаем для времени, необходимого для этого метода, следующую оценку: О (N2 log TV + N2qp (N)).
Простейший способ выполнить упомянутую проверку — это проверить, пересекает ли выбранное ребро каждое из k ребер, уже вошедших в триангуляцию. Так как каждая из этих элементарных проверок выполняется за постоянное время, то для Ф имеем y(k)=C\k (где С\— некоторая константа). Следовательно, полное время обработки равно 0(N3). 4 Более эффективный подход был предложен Джильбертом [Gilbert (1979)]. Цель, ставившаяся при разработке этого подхода, заключалась в том, чтобы сбалансировать работу по принятию решений (принадлежит ли выбранное ребро триангуляции) и работу по выбору ребер (просмотр ребер в порядке
порождается множество, содержащее все
ребер, соеди-
призводится выборка ребра из пула и каждое
Гл. 6. Близость: варианты и обобщения
увеличения длин). Ясно, что затраты на последнюю из работ составляют 0(N2 log N) независимо от того, используется предварительная сортировка или подход на основе пирамиды (пирамидальная сортировка) [Aho, Hopcroft, Ullman (1974)]. Поэтому нужно добиться, чтобы на обработку ребра требовалось не более О (log Л') операций. А это можно сделать следующим образом. Предположим, что выбрано ребро р\р-, (рис. 6.7(a)).
(а) (Ь)
Рис. 6.7. «Звезда из спиц» в точке р\. Ребра триангуляции показаны жирными отрезками.
Рассмотрим множество ребер, соединяющих р\ со всеми другими точками множества S, и обозначим его ЗВЕЗДА (pi). Это множество образует «звезду из спиц» в точке рь Эти спицы упорядочены в порядке обхода вокруг точки рь например против часовой стрелки, и делят полный угол в 2л радиан на (N— 1) секторов, или угловых интервалов. Если некоторое ребро pkpj уже включено в триангуляцию, то оно проходит через несколько последовательных секторов звезды в рь и то же самое имеет место для любой точки pi (l?=k,j). Заметим также, что никакие два ребра, уже включенные в триангуляцию, не пересекаются (по определению), так что ребра, попадающие в каждый угловой интервал, определяемый ЗВЕЗДА (pi), где 1=1, N, упорядочены1). Предположим, точка р, попала в сектор PjpiPk, определяемый ЗВЕЗДА (pi). Чтобы решить, следует ли включать ребро pip,- в триангуляцию, необходимо проверить, пересекает ли оно ребра триангуляции, прохо-
') Имеется в виду упорядоченность ребер внутри сектора по их расстоянию ОТ ТОЧКИ ре. — Прим. Пврвв.
6.2. Иланарные триангуляции
дящие через этот сектор, и, в частности, ближайшее из них к pi ребро. Таким образом, проверка пересечения сводится к частному случаю задачи определения положения точки на плоскости, когда в каждом секторе, определяемом ЗВЕЗДА (pi) (для всех /), необходимо хранить одно ребро триангуляции (называемое опорным ребром). Типичная ситуация показана на рис. 6.7(b), где затемнена область, допустимая для ребер триангуляции.
