Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Доказательство. Верхние оценки по времени и памяти были установлены ранее. Поэтому ограничимся доказательством оп-
i4U Рл. 8. Геометрия прямоуёольников
') Действительно, пусть Р[ := (х[ < х"), Р2 := (*" <ix'2), Р3 := (jsfOi) и Pt:= (х'^х^). В символической записи: РХР2 V Р3Р4 = Т -*=*-(Pt V Р3) • 1 (P» V Рз) (Pi V Pt) (Рг V Pi) =* Т. Поскольку Р, = Р3, Р, V Pt = Т, Р3 у Pt = Т, то имеем: PfP4 (Р2 V Р4) = Р*Р* = Т.
тимальности. Оптимальность по памяти очевидна. Что же касается оптимальности по времени, заметим, что задачу об уникальности элементов, для которой справедлива нижняя оценка й (N log N) на модели дерева решений (см. гл. 5), можно тривиально преобразовать в нашу задачу. На самом деле пусть даны N действительных чисел {гь zN) и выбран интервал [b, е]; по zt построим прямоугольник [b, е] X [zi, zi\ и применим к нему алгоритм поиска пересечений прямоугольников. Если пересечений не обнаружено, то все числа различны.
8.8.2. Другой подход к задаче о пересечении прямоугольников
Как отмечено в начале разд. 8.8.1, два интервала Я'=[л[, ^] и R" = [x"t пересекаются, если выполнено любое из следующих условий:
(1) л? (8.2)
(2) *f (8.3)
Легко видеть, что дизъюнкция двух предыдущих условий эквивалентна конъюнкции двух следующих условий '):
х" < х'2> х[ < х", которые можно тривиально преобразовать так:
— *2< — х", х[^х". (8.4)
Последнее условие выражает отношение «доминирования» < на плоскости (см. разд. 4.1.3) для точек (—х", х") и (— х'2, х\). В такой интерпретации задача определения всех пересекающихся пар интервалов из набора, в котором их Л7 штук, преобразуется следующим образом. Пусть задано множество $ = {/?(/> = [*</>, xf\. )'= 1, ..., N), состоящее из N интервалов; определим, во-первых, функцию а0: St-^E2, отображающую интервал [хих2] в точку (хих2) на плоскости (рис. 8.32; заметим, что точка (хих2) лежит выше биссектрисы х\ — х2 первого квадранта). Теперь определим отображение о': Е2-+ -+Е2, которое является преобразованием симметрии плоскости относительно оси х2 (т. е. точка (хи х2) отображается в точку (—xi, х2)). Наконец, определим отображение а": Е2-+Е2, ко-
8.8. Пересечения прямоугольников
443
торое является преобразованием симметрии плоскости относительно биссектрисы х2 = —хх второго квадранта (т. е. точка (—х\,х2) отображается в точку (—х2, Xi)). Для упрощения
\ р'={-х,,хг)
..slJ /
/
/
\
/
/
\
Рис. 8.32. Отображение интервала в две точки р' и р" на плоскости.
выражений обозначим через р' и р" композиции отображений а'сто и а"о/а0 соответственно. Убедимся в эквивалентности сле-
Рг=(3,7)
дующих соотношений, которая непосредственно следует из определений р', р" и (8.4):
/?«> л ф 0 р' (R{i)) > р" т р' (r{I)) > р" т.
Эта ситуация иллюстрируется на примере (рис. 8.33). Заметим, что каждая пара пересекающихся интервалов порождает две пары отношений доминирования.
444
Гл. 8. Геометрия прямоугольников
Теперь обратим внимание на задачу 0.8 (перечисление всех пересекающихся пар из множества прямоугольников 52— двумерный случай). Пусть дан произвольный прямоугольник R = [x\, х2]х[у\, г/2]; сначала отобразим его в пару точек P'{R) = {—X\,x2,—yx,y2) и р" (#) = (—х2, хи~~ у2, ух), лежащих в пространстве Е4 с координатными осями и\ и2, из, «4- Затем сформируем два множества точек в Е4:
S' = {p'(/?):/?e<52},
S" = {P" (#)
Вышеизложенные соображения свидетельствуют о том, что два прямоугольника Ri и R2 из 52 пересекаются тогда и только тогда, когда р'(/?,)> р" (#2) (или, что то же самое, р'(^г)>* y~p"(R\)). Поэтому задача 0.8 о перечислении всех пересекающихся пар является частным случаем следующей общей задачи о доминировании '):
Задача 0.9 (СЛИЯНИЕ ДОМИНИРОВАНИИ). Даны два множества точек Si и S2 в Еа. Надо найти все пары pi е S\ ир2е52 такие, что р, > р2.
О том, что наш случай является частным случаем этой общей задачи, свидетельствует тот факт, что у нас S' и 5" разделены двумя гиперплоскостями и\ -+- и2 = 0 и и3 + и4 = О в четырехмерном пространстве. Применяя алгоритм, который будет описан в следующем разделе, можно решить задачу о перечислении всех пересекающихся пар за время 0(N\og2N-\-+ s) вместо оптимального времени 9 (N log N + s), затрачиваемого алгоритмом из разд. 8.8.1. Разрыв между этими двумя оценками, вероятно, следует скорее из неспособности использовать специфику нашей постановки этой общей задачи, а не из неадекватности общего алгоритма решения задачи о слиянии доминирований.
8.8.3. Охват прямоугольников
Задача об охвате (или о принадлежности или включении, как часто говорят) прямоугольников является в некотором смысле частным случаем задачи о пересечении и формулируется следующим образом:
Задача О.10 (ОХВАТ ПРЯМОУГОЛЬНИКА). Дано множество S, состоящее из N изотетичных прямоугольников на пло-
') Заметим, что имеет место некоторая избыточность получающегося решения, и не только потому, что каждая искомая пара будет перечислена дважды, но еще и потому, что все тривиальные пары типа {R,R) также будут перечислены.
