Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Гл. 5. Близость: основные алгоритмы
Це, е') — Л означает, что отрезки е и е' не пересекаются. Как и ранее, U и г2— это два опорных отрезка и при этом t\ = pq. Ниже представлена реализация шага 3'.
1. begin pL:=p;
2. pR:=q;
3. е:=е;
4. v:=v*;
5. е? := первое ребро (открытой) границы V (pL);
6. ея:= первое ребро (открытой) границы V(pR);
7. repeat
8. while(/(e,eL) = A) do eL :— СЛЕДУЮЩИЙ]^]
(* посмотреть границу V(pL) *);
9. while(/(e,eR) = A) do ед := СЛЕДУЮЩИЙ2Ы
(¦посмотреть границу V(pR)*);
10. if(u ближе к I(e,eL), чем к l(e,eR)) then
11. begin и :=I(e,eL);
12. pL:= точка множества S, находящаяся по другую сторону от eL; _
13. е:= прямая, перпендикулярная pLpR и делящая его пополам;
14. el:~обратное к eL (* новое eL является ребром V(pL)*)
end
15. else begin v:= I(e,eR);
16. Pr'-— точка множества S, находящаяся по другую сторону от eR\ _
17. е:= прямая, перпендикулярная PlPr и делящая его пополам;
18. Cr'-— обратное к eR _end
19. unt\\{pLpR = t2)
end.
После инициализации (строки 1—6) начинается продвижение по цепи о (строки 7—19). Фактический механизм подвиже-ния по цепи описывают строки 8—18, при этом строки 8 и 9 описывают просмотр без возврата границ многоугольников V(pl) и V(pR) соответственно. Строки 11—14 и 15—18 отражают два взаимоисключающих случая изменения текущих значений параметров {v, pL, pR, eL, eR}, на выполнение каждого из которых требуется постоянное время. Так как диаграммы Vor (Si) и Vor(S2) вместе содержат не более 3N ¦—6 ребер, а цепь о содержит O(N) вершин, то полное время, необходимое для построения цепи а, является линейным. Подробное описание этой процедуры приведено в работе Ли [Lee (1978)].
5.6. Решение задан о близости с помощью диаграммы Вороного 269
Напомним, что для получения диаграммы Вороного необходимо удалить все ребра диаграммы Vor(Si), расположенные справа от а, и все ребра Vor(S2), лежащие слева от о. Операции по удалению ребер выполняются при обходе границ многоугольников по часовой стрелке и против часовой стрелки в процессе построения цепи а. Из всего сказанного следует, что для объединения Vor(Si) и Vor(S2) требуется линейное время. Завершим этот раздел следующей теоремой:
Теорема 5.15. Диаграмму Вороного для множества из N точек на плоскости можно построить за время 0(N\ogN), что является оптимальным.
Доказательство. Время, необходимое для выполнения рекурсивной процедуры объединения диаграмм, определяется рекуррентным соотношением T(N) = 1T{N/2)+ O(N) = 0(N log Л'). Оптимальность этой процедуры следует из теоремы 5.12.
5.6. Решение задач о близости с помощью диаграммы Вороного
В разделе 5.1 уже говорилось, что все представленные там задачи о близости можно эффективно решить с помощью диаграммы Вороного. В этом разделе мы более подробно обсудим это утверждение на примере задач Б.1, Б.2, Б.4 и Б.5.
Начнем с задачи ВСЕ БЛИЖАЙШИЕ СОСЕДИ (Б.2), для которой справедлива следующая теорема:
Теорема 5.16. Задача ВСЕ БЛИЖАЙШИЕ СОСЕДИ сводима за линейное время к задаче ДИАГРАММА ВОРОНОГО и, следовательно, может быть решена за время O(NlogN), что является оптимальным.
Доказательство. Согласно теореме 5.9, каждый ближайший сосед точки pt определяет ребро многоугольника V(i). Чтобы найти ближайшего соседа точки р,, достаточно лишь просмотреть каждое из ребер многоугольника V(i). Так как каждое ребро принадлежит двум многоугольникам Вороного, то ни одно из ребер не будет просматриваться более двух раз. Таким образом, имея диаграмму Вороного, можно найти всех ближайших соседей за линейное время.
Учитывая, что задача БЛИЖАЙШАЯ ПАРА (Б.1) сводима за линейное время к задаче ВСЕ БЛИЖАЙШИЕ СОСЕДИ, то очевидно, что диаграмма Вороного может быть также использована для оптимального решения задачи Б.1.
270
Гл. 5. Близость: основные алгоритмы
Решая задачу поиска ближайшего соседа (задачу Б.5), мы стремимся выполнить предварительную обработку исходного множества точек, с тем чтобы по возможности быстро осуществлять поиск ближайшего соседа точки q, задаваемой в запросе на поиск. Но поиск ближайшего соседа точки q эквивалентен поиску многоугольника Вороного, содержащего эту точку. Значит, предварительная обработка должна заключаться в построении диаграммы Вороного! Так как диаграмма Вороного является планарным прямолинейным графом, то для поиска на ней можно использовать любой из методов, представленных в разд. 2.2.2.
ЕДИНСТВЕННОСТЬ ЭЛЕМЕНТОВ -БЛИЖАЙШАЯ ПАРА (3.1)
ЕМОД (3.3)" ТРИАНГУЛЯЦИЯ (ЗЛ)
Связь задач о близости с основными задачами-прототипами (до-рнс. 5.6).
Теорема 5.17. Поиск ближайшего соседа можно выполнить за оптимальное время О (log Л7), использовав для этого память объемом O(N) и затратив на предварительную обработку время О (N log N).
Доказательство. На построение диаграммы Вороного затрачивается время O(NlogN), затем применяется теорема 2.7.
Ранее уже говорилось о том, что граф, двойственный диаграмме Вороного, является триангуляцией (триангуляция Делоне, см. теорему 5.11). Справедлива следующая теорема:
