Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
М— max xt + 1 \
(рис. 8.17; без потери общности предположим, что х\, ..., xN>0). Ясно, что F = Ri U ... U Rn не
ки, которая бы совпадала с нижней. Действительно, нетрудно обнаружить некоторую неэффективность поиска в поддеревьях для узлов отнесения с неполным статусом, поскольку затраты на прохождение по длинным путям приписываются только их конечным узлам. Это ограничение было преодолено Гютингом [Gutingf (1984)], построившим изумительную структуру данных для перечисления дыр в каждом поддереве за время, пропорциональное их числу, и тем самым создавшим
имеет дыр и что по контуру F можно получить упорядоченную последовательность {xi} за время O(N).
Для предыдущего алгоритма не удалось добиться верхней оцен-
Рис. 8.17. Преобразование процедуры СОРТИРОВКА к задаче поиска контура объединения прямоугольников, которое не имеет дыр.
Гл. 8. Геометрия прямоугс
асимптотически оптимальный алгоритм. Как и следовало предполагать, структура данных Гютинга чрезвычайно сложна в работе. За описанием метода Гютинга читатель может обратиться к его статье.
8.6. Замыкание объединения прямоугольников
Начнем с того, что дадим строгое определение замыканию объединения прямоугольников. Говорят, что две точки Pi = (xi,yi) и р2 = {х2,У2) на плоскости несравнимы, если они не связаны отношением «доминирования» (см. разд. 4.1.3), т. е. если (xi — х2) (г/i — у2) < 0. Если предположить без потери общности, ЧТО Х2>ХЬТ0, = СВ-сопряжение следуя удобной терминологии [Soisalon-Soininen, Wood (1982)], назовем ЮЗ- и СЪ-сопряжениями для pi и р2 две точки q\ = {ХиУ2) и q2={x2,y\)
_____________ соответственно (рис.
qrj = ЮЗ-сопряжение Рг^(хг>Уг) 8.18). Если задана пло-
ская область R (не обя-Рис. 8.18. Две точки Л и р2, несравнимые захеЛьно связная), ТО го-по доминированию, и сопряженные им '
точки qi и а7 ворят, что две точки сея-
заныв R, если существует кривая, полностью расположенная в одной из компонент связности R и соединяющая эти две точки. Введем теперь следующее определение:
Определение 8.2. Плоская область R называется СВ-замкну-той, если для любых двух несравнимых точек pi и р2, которые связаны в R, их СВ-сопряжения тоже расположены в R. Аналогично определяется и ЮЗ-замкнутая плоская область.
Определение 8.3. СВ-замыканием плоской области 5 называется наименьшая из СВ-замкнутых областей, содержащих S; она обозначается CB(S). Аналогично определяется и ЮЗ-замы-кание S, обозначаемое Ю3(5). СВЮЗ-замыканием (или просто замыканием для краткости) называется наименьшая область, содержащая S и такая, что она СВ-замкнута и ЮЗ-замк-нута одновременно; она обозначается СВЮЗ(5).
Теория замыкания была развита в работах [Yannakakis, Papadimitriou, Kung (1979); Lipski, Papadimitriou (1981); Soisalon-Soininen, Wood (1982)]. Для дальнейшего изложения нам необходимо подчеркнуть некоторые важные свойства изучаемых объектов.
8.6. Замыкание объединения прямоугольников
425
Говорят, что плоская кривая Г является х-монотонной, если для любых двух точек (хиу\) и (х2, г/2), лежащих на Г, справедливо условие: х2 > хх =>- г/2 5s У\- Если на плоскости задана запретная область D, то две плоские кривые Ti и Г2 называются гомотопными, если их можно совместить непрерывной деформацией, не пересекая D.
Если обозначить через R(F) минимальный изотетичный прямоугольник, охватывающий заданную (не обязательно связную) плоскую область F, то будут справедливы следующие очевидные соотношения:
^<=СВЮЗи(?) s[R(F).
Если СВЮЗ(/?) связно, то легко видеть, что СВ- и ЮЗ-угловые точки R(F) (рис. 8.19(a)) принадлежат этому замыканию F. Кроме того, для любой связной компоненты G из СВЮЗ (F)
Верхняя левая граница R(G) СВ-угол I
Нижняя правая граница
(Ь) (с)
Рис. 8.19. (а)—плоская фигура F и минимальный охватывающий ее (коор-о-ориентированный. — Перев.) прямоугольник R(F); (b)—связная i G СВЮЗ-замыкания плоской фигуры F; (с) — разделимость двух г связности СВЮЗС/7).
(рис. 8.19(b)) граница СВЮЗ(?) состоит из двух х-монотонных кривых, гомотопных соответственно верхнему левому и нижнему правому участкам границы R{G). Каждая из указанных двух х-монотонных кривых является экстремальной в собственном классе гомотопных кривых, не пересекающих G. Поэтому эти кривые можно называть верхним и нижним контурами замкнутой области СВЮЗ(/7). В общем случае для произвольной области F замыкание СВЮЗ(?) состоит из одной или более компонент; если число таких компонент больше единицы, то любые две из них можно разделить х-монотонной кривой (иначе будет нарушено условие замкнутости) (рис. 8.19(c)).
426
Гл. 8. Геометрия прямоугольников
Сойсалон-Сойнинен и Вуд установили также следующее важное свойство, справедливое для любой плоской фигуры F: СВЮЗ(?) = CB(K)3(F)) = ЮЗ(СВ(?)). (8.1)
Для практических приложений наиболее интересен случай, когда F является объединением изотетичных прямоугольников:
Задача 0.5 (ЗАМЫКАНИЕ ОБЪЕДИНЕНИЯ ПРЯМОУГОЛЬНИКОВ). Дан набор из N изотетичных прямоугольников. Надо построить замыкание их объединения.
