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

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

Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. Под редакцией Ю. М. Банковского — М.: Мир, 1989. — 478 c.
ISBN 5-03-001041-6
Скачать (прямая ссылка): vichgeometr.pdf
Предыдущая << 1 .. 158 159 160 161 162 163 < 164 > 165 166 167 168 169 170 .. 180 >> Следующая


8.8. Пересечения прямоугольников

445

скости. Надо перечислить все такие упорядоченные пары элементов 5, что первый элемент охватывает второй.

(Заметим, что, в то время как пересечение является симметричным отношением, охват является отношением частичного порядка.)

Опять введем обозначение 91 = {R{1), ..., RN}. В раннем решении задачи об охватах в качестве структур данных использовались деревья отрезков и регионов [Vaishnavi, Wood (1980)]; соответствующий алгоритм тратит время О (N log2 N 4- s) и использует О (N logjV) памяти. Теперь покажем, что преобразование задачи об охвате прямоугольника к задаче о доминировании точек позволяет достигнуть оптимальной оценки по памяти 9(Л7), сохранив прежнюю оценку по времени [Lee, Preparata (1982)].

Обозначая, как обычно, R(i) = [xf, xf] X [yf, yf], имеем, что RW сг ^(0 тогда и только тогда, когда выполнены одновременно следующие четыре условия:

Очевидно, что эти условия эквивалентны следующим:

-4» <-*<», xf^xf, - yf < - yf, yf < yf, (8.6)

которые выражают хорошо известное отношение доминирования между двумя четырехмерными точками, т. е.

Поэтому после отображения каждого прямоугольника R{i) 91 в соответствующую ему четырехмерную точку задача об охвате прямоугольника становится задачей о доминировании точек в четырехмерном пространстве1). А именно:

Задача 0.11 (ДОМИНИРОВАНИЕ). Дано множество точек 5 = {pi, ..., Pn} в d-мерном пространстве. Надо найти для каждой точки р,-е S такое подмножество ?>, = S, что Di= {р: р <= ^5, p<pi}.

Метод решения задачи 0.11, который будет описан, сильно напоминает (что не удивительно) метод, который был предложен ранее для решения задачи поиска максимумов на множестве векторов (в разд. 4.1.3). По-прежнему при d = 4 обозначим через «1, и2, Из и ц4 координаты в ?4. Первый предварительный шаг состоит в преобразовании каждого /?<«> ен 5? в точку p(R^) из Е4, где функция р( ) описывается приведенными выше соот-

4('><4'>, 4'><4«, 0<« yf < yf.

(8.5)

(-4», xf, -yf, у</>)<(_ 40, 4>, -yf, yf).

(8.7)

') Это соответствие было отмечено также в работе [Edelsbrunner, Over-mars (1982)].

446

Гл. 8. Геометрия прямоугольников

ношениями (8.6) и (8.7). Итак, получено множество S = = {p(R(-i)): ^We^i} = {pi, Pn}, индексы элементов которого следует изменить так, чтобы (i < /) (и\ (pi) < и\ (p/)). Теперь имеем

procedure ДОМИНИРОВАНИЕ Д1. (Разделение) Разбить S на (5Р S2), где Sl = {pl, ..., PLiV/2J},

а S2 = {Plnpj+v •' Pn}-

Д2. (Рекурсия) Решить задачу о доминировании точек на множествах Si и S2 независимо.

ДЗ. (Слияние) Найти все такие пары р( <( р/; у которых р» е е Si, а р/ <= S2.

Теперь обсудим реализацию шага ДЗ. Заметим, что на этом шаге решается задача 0.9 о слиянии доминирований. Для пары pi е Si и j3,gS2, поскольку по построению Wi(p<)^ «i(P/). то p{^Pi тогда и только тогда, когда ui(pi) ^ ш(р,) для 1 — 2, 3, 4. Поэтому шаг ДЗ фактически является трехмерной задачей. Опять воспользуемся методом «разделяй и властвуй» и обозначим через й2 медиану {и2(р«): p,eS2}.

procedure СЛИЯНИЕ-ДОМИНИРОВАНИЙ С1. (Разделение) Разбить Si на (Su, S,2), a S2~Ha (S2i, S22) так,

чтобы Sn = {р:ре Su ы2(р)<«2}, S2! = {р: р е S2, ы2(р)<"}.

a Si2 = Si —Sn, S22 = S2 — S2l. C2. (Рекурсия) Решить задачу слияния на парах множеств

(S„, S21) и (S,2, S22). СЗ. (Объединение) Найти все такие пары рг р/, у которых

pt<=Sn, a p; = S22.

Чтобы установить корректность описанного выше метода, заметим, во-первых, что S разбито на множества Sn, Si2, S2i и S22. Обращаясь к рис. 8.34 (где каждая подзадача обозначена дугой), видим, что на каждом из указанных четырех подмножеств решается задача о доминировании точек на шаге Д2; остается рассмотреть вопрос о дугах, соединяющих пары этих подмножеств. Две из шести пар — (Sn,Si2) и (S2i,S22) — также обрабатываются на шаге Д2; пары (Sn,S2i) и (Si2, S22) — на шаге С2; пара (Sn,S22) —на шаге СЗ, а пару (Si2, S2i) не надо рассматривать, поскольку для каждых р,- е Si2 и р/ е S2i верно, что ui(pi)^ ui(pj) и и2(р,)> "2(р/) • Отметим также, что шаг СЗ (Объединение) является двумерной задачей (на координатах ы3 и и4) •

Очевидно, что ключевой операцией всей задачи является реализация шага СЗ — двумерное слияние (или объединение). Действительно, все вычисление сводится к аккуратному выполнению последовательности шагов, подобных шагу СЗ; поэтому

8.8. Пересечения прямоугольников

447

в последующем надо сосредоточить внимание на разработке эффективной реализации шага «Объединение». Будет показано, что «Объединение» можно выполнить за время, линейно зависящее от размера входных данных, с затратой О (NlogN) времени на предварительную сортировку, которую можно отнести на счет общей процедуры. Позднее мы увидим, как этот результат влияет на оценку всей задачи.

Множества 5ц и S12, возникающие на шаге СЗ, являются наборами двумерных точек на плоскости («3, ы4). Создадим для

Рис. 8.34. Представление алгоритма для решения задачи СЛИЯНИЯ-ДОМИ-НИРОВАНИИ методом «разделяй и властвуй» в качестве ориентированного графа. Каждое подмножество является узлом, а каждая подзадача — дугой.
Предыдущая << 1 .. 158 159 160 161 162 163 < 164 > 165 166 167 168 169 170 .. 180 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed