Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
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. Представление алгоритма для решения задачи СЛИЯНИЯ-ДОМИ-НИРОВАНИИ методом «разделяй и властвуй» в качестве ориентированного графа. Каждое подмножество является узлом, а каждая подзадача — дугой.