Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
3.3. Алгоритм построения выпуклой оболочки
155
Лемма 3.1. Соединение двух разделимых выпуклых цепей, содержащих в сумме N точек, может быть выполнено за 0(\ogN) шагов.
Доказательство. Пусть даны две В-оболочки U\ и U2 и две вершины q\ е 1)\ и q2 е U2. Каждая из этих двух вершин может быть легко классифицирована по отношению к отрезку qxq2 как выпуклая, опорная или вогнутая (см. разд. 3.3.6, где дано объяснение этих терминов). В зависимости от этой классификации
Вогнутая Опорная Выпуклая
ftflflflfTfl
(смлЬ))
гПпЛпЛ
решение найдено
Рис. 3.21. (а) Все возможные случаи, возникающие при выборе некоторой вершины в W, и некоторой вершины в U2; (b) иллюстрация случая (вогнутая, вогнутая).
возможны девять случаев, схематически показанных на рис. 3.21(a). Пилообразной линией на рисунке обозначены подцепи, которые можно не рассматривать в дальнейшем, так как они не содержат опорных точек. Все представленные случаи понятны без дополнительных объяснений, за исключением случая (<7ь <7г) = (вогнутая, вогнутая), который более детально представлен на рис. 3.21(b). Пусть прямая h проходит через qx и ее правого соседа на Аналогично прямая 12 проходит через q2 и ее левого соседа на U2. Обозначим через р точку пересечения прямых U и 12. Напомним, что по предположению U\ и U2 разделимы вертикальной прямой I. Предположим для начала, что точка р находится справа от прямой /. Легко видеть, что опорная точка р\ может принадлежать лишь заштрихованной на
156
Гл. 3. Выпуклые оболочки: основные алгоритмы
рис. 3.21(b) области и что точка и имеет меньшую ординату, чем точка v. Отсюда следует, что любая вершина ц'\ принадлежащая правой относительно q2 подцепи, является вогнутой относительно отрезка q'q", где q' — произвольная вершина U\. Поэтому очевидно, что цепь справа от вершины q2 можно не рассматривать, но что касается цепи слева от вершины q\, то
Рис. 3.22. Множество точек на плоскости и соответствующая ему структура
для нее нельзя сделать подобное утверждение. Если точка пересечения р находится слева от разделяющей прямой /, то можно показать, что цепь слева от вершины q\ можно не рассматривать.
Во всех случаях удаляется некоторая часть одной или двух оболочек. Если этот процесс начинается с корневых вершин обоих деревьев, представляющих U\ и U2 соответственно, то, так как эти деревья являются сбалансированными, время выполнения функции СОЕДИНИТЬ(Ui, U2) составит O(logiV), где N—это, как обычно, суммарное число вершин в двух оболочках.
Имея функцию СОЕДИНИТЬ, можно анализировать процесс динамической поддержки выпуклой оболочки на плоскости. Типичная ситуация показана на рис. 3.22. Номера точек соответствуют порядку, в котором они добавлялись к множеству.
3.3. Алгоритм построения выпуклой оболочки
157
В структуре данных Т каждый лист соответствует точке, а каждый узел, не являющийся листом, соответствует мосту (т. е. опорному отрезку, соединяющему две оболочки). Для каждого такого узла указана пара Q[v], J[v]. Легко понять, что структура данных описывает некоторое свободное дерево на текущем множестве точек, которое называется деревом оболочки. Читателю
следует затратить немного времени, чтобы полностью разобраться во всех деталях рис. 3.22.
Предположим теперь, что мы хотим вставить новую точку р. Процедура вставки должна не только давать сбалансированное по высоте дерево Т, используя для этого обычный метод балансировки [Reingold, Nievergelt, Deo (1977)], но и делать все необходимое для того, чтобы была полная уверенность в том, что сцепляемая очередь, связанная с каждой вершиной, по-прежнему удовлетворяет требованиям, указанным в определении структуры данных Т. Предположим для простоты, что балансировка не требуется (все действия по балансировке просто увеличивают не имеющим значения способом число узлов, подле-
Вставить р,3
Рис. 3.23. Вставка точки р13. При вставке затрону 12), 3}, {(2), 2}, {(0), 1}, {(5), 1}, {(10), 1}, {13}.
тронуты узлы: {(И, 4, 1, 13,
158
Гл. 3. Выпуклые оболочки: основные алгоритмы
жащих обработке, не приводя к каким-либо принципиальным отличиям). Поэтому будем считать, что точка р13 добавляется к множеству точек, представленному на рис. 3.22, как это показано на рис. 3.23. На этом рисунке показано также состояние структуры данных Т после вставки точки р[3. Заметим, что р\ъ однозначно определяет путь из корня дерева Т к листу, в который должна быть вставлена рп- Двигаясь по этому пути из корня, в каждом узле, находящемся на этом пути, мы собираем В-оболочку, относящуюся к этому узлу, и затем, используя параметр / [и], разбиваем ее на части, чтобы передать двум потомкам этого узла соответствующие им части. Действуя таким способом, будем иметь в каждом узле и, являющемся братом одного из узлов на этом пути, полное представление U(и) в виде сцепляемой очереди Щи]. Более формально такой спуск по дереву с целью вставки точки р осуществляется путем вызова процедуды СПУСК(корень(7'), р). СПУСКА, р) — это рекурсивная процедура, использующая функции РАСЦЕПИТЬ и СЦЕПИТЬ, обсуждавшиеся ранее. Приведем описание этой процедуры:
