Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Т := ЛДЕРЕВО(с) else Т := ПДЕРЕВО(с) /:=ЛЕВЫЙ-ПОИСК(Г)
end; return /
Очевидно, что функция ЛЕВЫЙ-ПОИСК проходит по дереву Т некоторый путь, затрачивая в каждом узле ограниченное время на классификацию соответствующей узлу вершины. То же самое имеет место и для
Расцепить Расцепить I Сцепить
Удалить г
L Удалить
функции ПРАВЫЙ-ПОИСК. Теперь рассмотрим случаи
1, 3, 5 и 7. В каждом из этих случаев обе вершины / и г следует искать в одном и том же поддереве корня, если они только существуют (следует отметить, что в случаях 1 и 7 точка р может быть внутренней точкой Р). Таким образом, в каждом случае процедура поиска рекурсивно вызывает себя для поиска в поддереве текущего дерева') (выбирается поддерево, соответствующее последовательности, обведенной на рис. 3.16 штриховой линией) до тех пор, пока не встретится один из случаев
2, 4, 6 или 8. В этом месте инициируется раздельный поиск с помощью функций ЛЕВЫЙ-ПОИСК и ПРАВЫЙ-ПОИСК. Если в процессе поиска будет достигнут лист дерева Т и при этом не имел место ни один из случаев 2, 4, 6 или 8, то точка р является внутренней для многоугольника. В заключение отметим, что в самом общем случае можно наглядно представить процесс поиска опорных прямых, прослеживая начальный участок пути из корня Т до узла с, в котором происходит разветвление пути на два. Учитывая, что
') Для того чтобы каждое рекурсивное обращение выполнялось за время 0(1), необходимо, чтобы элементы m и М поддерева были легко доступны. Для М, являющегося корнем дерева, это не составляет проблемы. Однако элемент m в правом поддереве будет достижим из текущего корня, если «прошить» дерево, т. е. ввести указатель СЛЕДУЮЩИЙ, связывающий вершину v со следующей за ней вершиной vi+l на границе многоугольника.
Рис. 3.17. Для удаления точек, оказавшихся внутри выпуклой оболочки, требуется выполнить различные действия в зависимости от относительного положения вершин I и г.
3.3. Алгоритм построения выпуклой оболочки 151
дерево Т сбалансировано и содержит не более i < N вершин, а на обработку в каждом узле требуется ограниченное время, получаем для времени поиска оценку О (log i).
Чтобы завершить описание, рассмотрим процедуру перестройки многоугольника С,-_ь выполняемую, если точка р,- является внешней для него. Вершины между I и г должны быть удалены, a pi должна быть вставлена на их место. В зависимости от того, предшествует вершина / вершине г в дереве Т или нет, требуется выполнить немного различные действия (рис. 3.17). В первом случае необходимо дважды выполнить операцию расцепления и один раз сцепления; во втором случае только дважды выполняется операция расцепления.
Как уже упоминалось ранее, обе операции РАСЦЕПИТЬ и СЦЕПИТЬ выполняются за время O(logt'). В результате, учитывая, что коррекция выпуклой оболочки может быть выполнена за время О (log i). имеем следующую теорему:
Теорема 3.11. Выпуклая оболочка множества из N точек на плоскости может быть найдена с помощью открытого алгоритма за время Q(NlogN) со временем коррекции Q(\ogN), т.е. может быть построена в реальном времени.
3.3.7. Обобщение: поддержка динамической выпуклой оболочки
Описанный в предыдущем разделе метод можно рассматривать как метод поддержки структуры данных, описывающей выпуклую оболочку множества точек в случае, когда допускается лишь операция добавления (вставки) точек. При этом вполне естественно возникает вопрос: можно ли разработать структуру данных, организующую множество точек на плоскости и описывающую их текущую выпуклую оболочку, в предположении, что допускаются не только добавление (вставка), но и удаление точек?
Как можно было ожидать, на этот вопрос нет простого ответа. В самом деле, в то время как в открытом алгоритме построения выпуклой оболочки из разд. 3.3.6 точки, про которые становится известно, что они являются внутренними точками текущей выпуклой оболочки, навсегда исключаются из рассмотрения, в этой новой ситуации необходимо с одинаковой тщательностью организовывать все точки, содержащиеся на текущий момент в множестве, так как удаление некоторой точки текущей выпуклой оболочки может привести к тому, что несколько внутренних точек станут граничными точками новой выпуклой оболочки (рис. 3.18). Эта задача рассматривалась Овермарсом и Ван Леювеном. Приведем формальную постановку этой задачи;
152
Гл. 3. Выпуклые оболочки: основные алгоритмы
Задача В07 (ПОДДЕРЖКА ОБОЛОЧКИ). Заданы изначально пустое множество 5 и последовательность из N точек
Точна, становящиеся граничными.
Рис. 3.18. При удалении точки />3 точки р{ и р2 становятся граничными точками выпуклой оболочки.
(Ри Р?, ..., Pn), каждая из которых либо добавляется к множеству 5, либо удаляется из него (разумеется, точка может быть удалена лишь при условии, что она содержится в S). Требуется поддерживать выпуклую оболочку множества 5.
Теперь мы проиллюстрируем очень интересное решение этой задачи, предложенное О марсом и Ван Леювеном [Over mars, van Leeuwen (1981)] Прежде всего мы используем тот факт, что граница выпуклой оболочки представляет объединение двух (выпуклых) монотонных ломаных линий (цепей). Эти ломаные огра-точек. ничивают оболочку сверху и