Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Рис. 2.10. Суммарное число отрезков в полосах может достигать 0(N2).
Заметим, что если ребро ППЛГ проходит через несколько полос, то эти полосы следуют одна за другой. Это наблюдение и является тем ключом, позволяющим сократить время предобработки, поскольку можно воспользоваться методом заметания плоскости (см. разд. 1.2.2). Напомним, что алгоритм пло-ского заметания характеризуется двумя основными структурами данных: (1) списком точек событий, т.е. последовательностью
2.2. Задачи локализации ючки
позиций, назначаемых для заметающей прямой; (2) статусом заметающей прямой, т. е. описанием пересечения заметающей прямой с заметаемым геометрическим объектом. В нашем случае, если плоское заметание проводить, скажем, снизу вверх, то моментальным статусом заметающей прямой будет упорядоченная слева направо последовательность реоер графа, пересекающих ту полосу, где находится заметающая прямая. Эта последовательность, т. е. порядок ребер слева направо, не изменяется внутри данной полосы, но изменяется на границе со следующей полосой, когда достигается v — новая вершина ППЛГ. Ясно, что в этой точке рёбра, оканчивающиеся в_^.^удаляются и заме: няютёя теми, ШтЬ^Ш^ааяШ^ются^в v. Статус заметающей пря-яой .\ГОжно хранить в форме дерева, сбалансированного по высоте (т. е. 2-3 дерева), которое, как хорошо известно, допускает реализацию операций вставить и удалить за время, пропорциональное логарифму его размера. Добавим, что заметающая прямая сканирует полосы в восходящем порядке, т. е. спи-сок точек событий — это просто перечисленные снизу вверх вер-"" шины ППЛГ. В каждой точке события статус заметающей прямой корректируется и запоминается; ясно, что этот статус есть просто последовательность отрезков внутри вышележащей полосы. С точки зрения затраты ресурсов работа состоит во вставлении и удалении каждого из ребер графа — со стоимостью О (log TV) на одну операцию — и в запоминании статуса; на первое уйдет O(NlogN) времени, поскольку по теореме Эйлера в yV-вершинном планарном графе O(N) ребер, а последнее потребует 0(N2) памяти, как указано выше. Алгоритм предобработки будет интуитивно понятнее, если считать ребра ориентированными снизу вверх. Вершины, упорядоченные по возрастанию у, запоминаются в массиве вершина; B[i] — множество ребер, инцидентных вершиней снизу (входящие ребра) и упорядоченных по углу против часовой стрелки; A[i] — множество ребер, исходящих из вершины (t) и упорядоченных по чяспипй стрелке Ребра запоминаются в Сбалансированном по высоте дереве ^-.'Предлагается следующий алгоритм:
procedure предобработка-для-локализации-
точки-на-плоскости
begin вершина[1 : 2N] := вершины G, упорядоченные по возрастанию у; L:= 0;
for i:=2 until N do
begin УДАЛИТЬ(БИ) из L; ВСТАВИТЬ(ЛИ) в L; Запомнить L
end
end.
3 Зак. 1075
Гл. 2. Геометрический поиск
Итак, сформулируем теорему:
Теорема 2.4. Локализацию точки в N-вершинном планарном подразбиении можно реализовать за время О (log N) с использованием О (N2) памяти, если О (Л72) времени ушло на предобработку.
Хотя данный метод обладает оптимальной оценкой времени запроса, однако его время предобработки и — в еще большей степени — его затраты памяти чрезмерны и для многих приложений недопустимы. Было высказано предположение (Shamos (1975а)], что затраты памяти можно сократить до 0(N), хотя это может потребовать увеличения времени запроса до 0(log2 N). Вскоре эта гипотеза подтвердилась, что и будет показано ниже. Этот почти оптимальный метод стал основой для дальнейших существенных продвижений [Edelsbrunner, Guibas, Stolfi (1985)].
2.2.2.2. Метод цепей
В то время как в методе полос эффективность люиска достигается J5лaгo:дjylя,..^екшшрзщши исходного подразбиения н1Гтр1ггпяШй'Гв методе цепей, предложенном Ли и Препаратой [Lee, Preparata (1978)], эта же цель достигается благодаря использованию в качестве базовой компоненты нового типа многоугольников, называемых монотонными и определяемых ниже.
Ключевым в этом методе является определяемое здесь понятие «цепи».
Определение 2.1. Цепью С = (ии ..., ир) называется ППЛГ с вершинами {ии ..., ир) и ребрами {(«,-, t = 1, ...
.... р-1}.
Другими словами, цепью в силу данного определения является плоская укладка теоретико-графовой цепи, которую иногда называют также ломаной линией (рис. 2.11(a)).
Рассмотрим планарное подразбиение, определяемое ППЛГ G. Предположим, что в G найдена цепь С (подграф G) одного из следующих типов: (1) С является циклом или (2) оба конца и\ и Up из С лежат на границе бесконечной области. В последнем случае дополним С с обоих концов полубесконечными параллельными ребрами. Теперь цепь каждого типа делит исходное подразбиение на две части. Более того, мы скоро увидим, что процедура определения того, по какую сторону от С лежит пробная точка г, именуемая процедурой дискриминации z относительно С, довольно проста. Далее, если удастся выбрать С так, чтобы указанные части были сравнимы по сложности, то, рекурсивно повторяя деления, мы получим метод локализации точки, который требует логарифмического числа дискримина-
