Научная литература
booksshare.net -> Добавить материал -> Математика -> Препарата Ф. -> "Вычислительная геометрия: Введение" -> 150

Вычислительная геометрия: Введение - Препарата Ф.

Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. Под редакцией Ю. М. Банковского — М.: Мир, 1989. — 478 c.
ISBN 5-03-001041-6
Скачать (прямая ссылка): vichgeometr.pdf
Предыдущая << 1 .. 144 145 146 147 148 149 < 150 > 151 152 153 154 155 156 .. 180 >> Следующая


Следствие 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 дерево отрезков позволяет воспользоваться когерентностью смежных сечений путем эффективного вычисления текущего сечения за счет простой корректировки предыдущего сечения.) Эта идея была впоследствии перенесена на случай
Предыдущая << 1 .. 144 145 146 147 148 149 < 150 > 151 152 153 154 155 156 .. 180 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed