Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
тельно, общая оценка времени, потребляемого главным циклом while, равна 0((JV + /С) log /V), что, очевидно, превосходит оценку шага начальной сортировки. Отсюда имеем следующую теорему:
Теорема 7.7 [Bentley, Ottmann (1979)]. На множестве из N отрезков можно обнаружить К пересечений за время 0((N-\-+ K)\ogN).
Заметим, что вышеописанный алгоритм решает следующую задачу (отличную от поставленной в начале данного раздела):
Задача С.1.2 (ПЕРЕСЕЧЕНИЕ ОТРЕЗКОВ). Даны N прямолинейных отрезков. Надо найти все их пересечения.
Наиболее важной чертой приведенного выше алгоритма является простота, однако, характеристики его работы не оптимальны. Действительно, нижняя оценка по времени для этой задачи равна Q(K + N\ogN) поскольку компонента Q(N\ogN) следует из теоремы 7.6, а О (К) тривиально получается из оценки объема выводного файла. Понятно, что такое несовпадение оценок привлекло к себе большой интерес исследователей, который достиг кульминаций после серии последовательных улучшений построения алгоритма с оптимальной временной оценкой Q(K + NlogN). Это сделали Чазелле и Эдельс-бруннер [Chazelle, Edelsbrunner (1988)]. Эти результаты будут далее проиллюстрированы в разд. 7.4.
Если отказаться от мысли найти все пересечения и заняться соответствующей задачей проверки («Найти одно пересечение,
= 0(logN) времени, поскольку
Следова-
7.2. Плоские приложения
349
если их число больше нуля»), то все сильно упрощается. Фактически можно работать как в одномерном алгоритме. Однако в данном случае нельзя ограничиться единственным объектом в структуре данных: она должна быть пригодна для хранения полного упорядочения на множестве отрезков, пересеченных заметающей прямой, и совпадает с использованным ранее словарем SB. Главное различие алгоритмов построения и проверки пересечений заключается в структуре данных для списка точек событий, который в последнем случае является простым массивом, содержащим 2N исходных концевых точек. Имеем следующий алгоритм:
procedure ПРОВЕРКА-ПЕРЕСЕЧЕНИЯ-ОТРЕЗКОВ begin сортируем лексикографически 2N концов по х и у и помещаем их в действительный массив ТОЧКА[1 : 2Щ; for i := 1 until 2N do Л begin p:= ТОЧКАМ;
s:= отрезок, концом которого является р; if (р — левый конец) then begin ВСТАВИТЬ^,.г); s, :=WhJ\{s,2); s2:= ПО R(s,&);
if (s{ пересекает s) then вывод (s^s) if (s2 пересекает s) then вывод (s2,s)
end;
else (* p — правый конец s *) begin Sl-—HAH(s,gy, s2 := ПОJX(s,2);
if (s, пересекает s2) then вывод (S[,s2); УДАЛИТЬ^,2>)
end
end
end.
Следующая теорема устанавливает корректность этого алгоритма:
Теорема 7.8. Алгоритм ПРОВЕРКА-ПЕРЕСЕЧЕНИЯ-ОТРЕЗКОВ находит пересечение, если оно существует.
Доказательство. Поскольку алгоритм сообщает о пересечении, только если оно действительно найдено, то он не объявит о ложном пересечении, и поэтому заслуживает внимания лишь тот случай, когда существующее пересечение может остаться необнаруженным. Покажем, что данный алгоритм корректно находит самую левую из существующих точек пере-
350
Гл. 7. Пересечены
сечения — qt. Действительно, если qL совпадает с левым концом р какого-нибудь отрезка, то qL обнаруживается при обработке р. Поэтому предположим, что qL — не левый конец отрезка. Слева от qL структура данных 3? содержит корректное представление отношения >х. Поскольку слева от qL существует некий небольшой непустой интервал абсцисс, на котором два отрезка, пересекающиеся в qL, становятся смежными, то qL обнаруживается так, как и ожидалось. Теорема доказана.
Несмотря на то что вышеописанный алгоритм кажется простым, он обладает рядом любопытных свойств. Так, хотя самое левое пересечение действительно находится, однако это вовсе не означает, что оно найдено первым. (Читатель может проверить свое понимание этого алгоритма, точно указав, какое пересечение обнаруживается первым.) Поскольку этот алгоритм выполняет только O(N) проверок пересечения, он также может не обнаружить некоторые пересечения. Главный блок // (проверка пересечений) выполняется, очевидно, за время O(logjty) в худшем случае. Итак, получаем в заключение следующую теорему (повторим опять, что оптимальность следует из теоремы 7.6):
Теорема 7.9. Факт пересечения какой-нибудь пары из N отрезков на плоскости можно определить за оптимальное время В (NlogN).
Из этого результата немедленно вытекает
Следствие 7.1. Следующие задачи можно решить за время О (NlogN) в худшем случае:
Задача С.2.2 (ПРОВЕРКА ПЕРЕСЕЧЕНИЯ МНОГОУГОЛЬНИКОВ). Пересекаются ли два заданных многоугольника?
Задача С.2.3 (ПРОВЕРКА ПРОСТОТЫ МНОГОУГОЛЬНИКА). Прост ли заданный многоугольник?
Задача С.2.4 (ПРОВЕРКА УКЛАДКИ ГРАФА). Пересекаются ли ребра заданной прямолинейной укладки планарного графа?
Другие результаты, полученные с использованием вариантов процедуры ПРОВЕРКА-ПЕРЕСЕЧЕНИЯ-ОТРЕЗКОВ, можно найти в работе [Shamos, Ноеу (1976)]. Процитируем оттуда
Следствие 7.2. Факт пересечения какой-нибудь пары из N окружностей можно определить за время О (N log N).
