Научная литература
booksshare.net -> Добавить материал -> Математика -> Препарата Ф. -> "Вычислительная геометрия: Введение" -> 55

Вычислительная геометрия: Введение - Препарата Ф.

Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. Под редакцией Ю. М. Банковского — М.: Мир, 1989. — 478 c.
ISBN 5-03-001041-6
Скачать (прямая ссылка): vichgeometr.pdf
Предыдущая << 1 .. 49 50 51 52 53 54 < 55 > 56 57 58 59 60 61 .. 180 >> Следующая


Т := ЛДЕРЕВО(с) 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)] Прежде всего мы используем тот факт, что граница выпуклой оболочки представляет объединение двух (выпуклых) монотонных ломаных линий (цепей). Эти ломаные огра-точек. ничивают оболочку сверху и
Предыдущая << 1 .. 49 50 51 52 53 54 < 55 > 56 57 58 59 60 61 .. 180 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed