Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
СТАТУС[ПСЫН[у]] = пуст) then СТАТУОД := пуст . else СТАТУС[у] := неполон
') Строго говоря, эта процедура реализует лишь первый этап построения контура объединения прямоугольников: она строит множество вертикальных ребер этого контура. — Прим. перев.
8.5. Контур объединения прямоугольников 421
Теперь опишем подпрограмму ВКЛАД: function ВКЛАД (й, e;v)
(* данная подпрограмма использует внешний параметр СТЕК. В начале работы при вызове данной подпрограммы с параметрами ВКЛАД(Ь, е; корень (Г)) из главной процедуры СТЕК пуст. Подпрограмма заносит в СТЕК последовательность отрезков, представляющих собой [Ь, е] Г| вклад (v). Содержание СТЕКА возвращается при вызове ВКЛАД (Ь, е; корень (7)) *) begin
1. if СТАТУС[о] ф полон) then
2. if (b^B[v)) and(?[y)<e) and(CTATYC[o] = пуст) then
(* вклад отрезка [S[a],?[y]] уже учтен*)
3. begin if (B[v] = вершина (СТЕКА)) then («объедине-
ние смежных отрезков *)
4. удалить вершину (СТЕКА)
5. else СТЕК«*=?[а] (* начало ребра*);
6. C7EK<=E[v] (*текущий конец ребра*) end;
7. else begin if (b < l(B[v] + E[v])/2}) then
8. ВКЛАДА,e; ЛСЫН[о]);
9. if(L(fl[o] + ?[o])/2J<e) then 10. ВКЛАДА,e; ПСЫЩо])
end
end.
Маршрут, пройденный процедурой ВКЛАД в дереве отрезков (т. е. последовательность обработанных ею узлов), существенно пересекается с аналогичной последовательностью, соответствующей процедуре ВСТАВИТЬ (или УДАЛИТЬ), однако есть два важных отличия, которые сейчас будут обсуждены на примере процедуры ВСТАВИТЬ (без потери общности). Хорошо известно, что маршрут процедуры ВСТАВИТЬ имеет типичную структуру, которая уже изучалась в разд. 1.2.3.1 и воспроизведена на рис. 8.16 для удобства читателей). Начальный путь (возможно, пустой) РНач приводит к узлу, именуемому развилкой, из которого выходят два (возможно, пустых) пути Рл и РП; изображено также множество узлов отнесения, определяющих сегментацию вставленного интервала. Подпрограмма ВКЛАД тоже проходит Рнач, Рл и Pnj однако если какой-нибудь узел на любом из этих путей имеет полный СТАТУС, то проход по этому пути прерывается (строка 1 в подпрограмме ВКЛАД). Это происходит потому, что «/-интервал отрезка s (или участок этого интервала) «перекрывается» 3 и его вклад в s (] 3 пуст. Когда СТАТУС любого назначенного узла и, которого достигла подпрограмма ВКЛАД, не является полным, тогда, если он пуст,
422
Гл. 8. Геометрия прямоугольников
вклад всего отрезка [В [v], E\v]] уже учтен; в противном случае ВКЛАД начинает поиск в поддереве с корнем v (строки 7—10) (это происходит, конечно, только если СТАТУС [и] неполон). Этот поиск является наиболее времяемкой частью всей задачи, как будет сейчас показано. На рис. 8.16(b) видно, что для каждого отрезка и из ^fll^M, Я [и]] существуют два уникальных узла в поддереве с корнем и, которые соответствуют самому левому и самому правому участкам и. Простой
Рис. 8.16. (а)—типичная подструктура в Т, пройденная процедурой ВСТАВИТЬ или УДАЛИТЬ; (Ь) — для каждого узла отнесения с неполным СТАТУСОМ, достигнутого подпрограммой ВКЛАД, производится последующий проход по всем путям, ведущим к узлам, которые соответствуют концам отрезков из Э П №], ?[»]].
анализ показывает, что подпрограмма ВКЛАД выполняет прохождение в прямом порядке путей, ведущих из о к указанным узлам, при этом затрачивается фиксированное количество работы на каждый пройденный узел и, возможно, на его братьев по дереву. Поэтому суммарная работа пропорциональна сумме длин этих путей. Согласно общему свойству двоичных деревьев [Lipski, Preparata (1980)], если в поддереве существует v концевых узлов, то искомая суммарная длина путей ограничена величиной v log(16iV/v). Обозначим через п< число отдельных кусков в Si, П 3^> где s, — это j-я сторона прямоугольника, кото рую обрабатывает данный алгоритм. Тогда общая работа подпрограммы ВКЛАД ограничена величиной
Узел отнесения V СТАТУС [и] неполон
n V г ^ n , 32/V2
8.5. Контур объединения прямоугольников
423
где р обозначает суммарное число ребер контура, а С— константа. Объединяя последнюю оценку с результатами анализа процедур ВСТАВИТЬ и УДАЛИТЬ, а также с оценкой работы второго этапа данного метода (на котором соединяются горизонтальные и вертикальные ребра), получаем следующую теорему:
Теорема 8.4. Контур объединения N изотетичных прямоугольников, состоящий из р ребер, можно получить за время 0(NlogN + plog(N*/p)).
Если поставить вопрос об оптимальном алгоритме, то заметим, что известна нижняя оценка для этой задачи, равная Q(N log N-j-р). Действительно, О(р) — тривиальная оценка, следующая из размера контура, a Q (NlogN)— это нижняя оценка, полученная преобразованием СОРТИРОВКИ к построению контура (свободного от дыр) объединения прямоугольников, как вытекает из следующей теоремы:
Теорема 8.5. Сложность построения контура для F = R\ U U -#2 U ••• U Rn, где F не содержит дыр, равна Q(Nlog N) при работе с моделью дерева решений.
Доказательство. Покажем, что задача сортировки N чисел х{, xN преобразуется за время O(N) в нашу задачу. Действительно, пусть для заданного х,- Ri будет декартовым произведением х-интервала [0, х{\ и у-ин-тервала [0,M — Xi], где "
