Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Следствие 8.1. Любой алгоритм, который использует модель алгебраического дерева решений, для определения существования некоторой пары чисел из N-элементного множества, удаленных друг от друга на расстояние, меньшее чем е, затратит Q (N log N) проверок.
Следствие 8.1 доказывает оптимальность результата Кли для задачи о вычислении меры в случае одного измерения, но оставляет открытым вопрос об оптимальной оценке при d > 2.
Рис. 8.8. Применение метода плоского заметания к задаче определения меры объединения прямоугольников для случая двух измерений.
Бентли [Bentley (1977)]') взялся за эту задачу и преуспел в создании оптимального алгоритма для вычисления меры объединения при d = 2. Его подход является простой и разумной модификацией одномерного метода. В частности, при одном измерении длина интервала [X[i— 1], X[i) ] добавляется к искомой мере (строка 6 в алгоритме МЕРА-ОБЪЕДИНЕНИЯ-ИНТЕРВАЛОВ) в зависимости от того, будет ли хотя бы один отрезок накрывать его или нет, или, что то же самое, будет ли параметр С ненулем или нулем соответственно. Следовательно,
- Заметающая прямая
') Этот результат изложен также в работе [Van Leeuwen, Wood (1981)].
Гл. 8. Геометрия прямоугольников
необходимо знать только значение С (строка 7). В случае двух измерений (рис. 8.8) вертикальная полоса, заключенная между X[i—1] и X[i], вносит в меру объединения прямоугольников вклад, равный величине (X[i] — X[i— 1] )m,-, где m,- —длина пересечения произвольной вертикальной прямой из этой полосы с объединением прямоугольников. Поэтому величина пи (являющаяся константой и равная 1 в случае одного измерения)— это ключевой параметр для двумерной техники. Если бы т, можно было вычислять и корректировать за время, не превышающее O(logyV), то времена сканирования и предварительной обработки были бы равны и был бы получен оптимальный алгоритм о оценкой Q(N\ogN).
Поскольку ординаты горизонтальных сторон прямоугольников известны заранее, то определение т, можно реализовать посредством дерева отрезков (см. разд. 8.3). Вспоминая общий формат элементарных операций на дереве отрезков ВСТАВИТЬ И УДАЛИТЬ (см. разд. 8.3), определим для текущего приложения следующий дополнительный параметр узла:
m(?>):= вклад интервала [.В [у], ? [и] ] в величину тщ. Вычисление m[v] проводится следующей процедурой (вызываемой в строке 4 из процедуры ВСТАВИТЬ): procedure КОРРЕКТИРОВАТЬ(о) begin if(C[v]?=0) then m[v] := E[v] — B[v]
else if (а не лист) then m[v] := т[ЛСЫН[и]] + /я[ПСЫН[о]]
else m[v] :=0
end.
Ясно, что m,¦ = m [корень дерева отрезков]. Как общий параметр C[v], так и специальный параметр m[v] можно легко корректировать (за константное время на один узел) при вставке или удалении одного отрезка (вертикальной стороны прямоугольника) из дерева отрезков. Итак, корректировку дерева отрезков и вычисление т; можно реализовать за время О (log Л7) для одной вертикальной стороны прямоугольника; тем самым достигается ранее поставленная цель. Теперь можно сформулировать алгоритм, где 6, и е, обозначают соответственно минимальную и максимальную ординаты вертикальной стороны, имеющей абсциссу X[i]. (Заметим, что этот алгоритм является непосредственным обобщением одномерного алгоритма, приведенного ранее.)
procedure МЕРА-ОБЪЕДИНЕНИЯ-ПРЯМОУГОЛЬНИКОВ 1. begin Х[\ : 2N] := упорядоченная последовательность абсцисс вертикальных сторон;
S.4. Мера и периметр объединения прямоугольников 409
2. Х[0]:=Х[1]\
3. го := 0;
4. построить и инициализовать дерево отрезков Г для ординат сторон прямоугольника;
5. for i := 1 until 2N do
6. begin m* := т[корень(Г)];
7. m:=m + m'(X[i]-X[i- I]);
8. if (X[t] — абсцисса левой стороны) then
ВСТАВИТЬ (ft,-, e,; корень(Г))
9. else УДАЛИТЬ(й,,в,; корень(Г)) end
end.
Завершим это обсуждение следующей теоремой:
Теорема 8.1. Меру объединения N изотетичных прямоугольников на плоскости можно вычислить за оптимальное время 9(/V log/V).
Возвращаясь к последнему алгоритму, мы сразу же увидим, что он относится к категории плоского заметания (см. разд. 8.3), где списком точек событий служит массив X[l:2N], а статус заметающей прямой задается деревом отрезков. Подобная реализация допускает непосредственное обобщение этого метода на случаи более чем двух измерений. Действительно, техника заметания позволяет преобразовать исходную d-мерную задачу (на N гиперпрямоугольниках в Ed) в «последовательность», состоящую из N штук (d—1)-мерных подзадач (каждая на не более чем N гиперпрямоугольниках в Ed~l). Для d = 3 эти подзадачи становятся двумерными, и по теореме 8.1 каждую из них можно решить за время О (NlogN); поэтому задачу-!) мере объединения при трех измерениях можно решить за время 0(N2 log N). Это устанавливает базис для индуктивного доказательства, приводящего к следствию 8.2.
Следствие 8.2. Меру объединения N изотетичных гиперпрямоугольников в пространстве d^2 измерений можно вычислить за время О (Nd~l log N).
Сильным недостатком описанного метода при d ^ 3 является тот факт, что при заметании мы не смогли использовать «когерентность»1) между двумя последовательными сечениями. (При d = 2 дерево отрезков позволяет воспользоваться когерентностью смежных сечений путем эффективного вычисления текущего сечения за счет простой корректировки предыдущего сечения.) Эта идея была впоследствии перенесена на случай