Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
7
5
4
1
8
2
НАЧ
3
7
5
4
®
г
НАЧ
3
(НАЧ)
5
4
3
г
НАЧ
3
НАЧ
5
4
1
3
г
НАЧ
3
НАЧ
®
4
1
3
2
НАЧ
3
НАЧ
3
©
3
г
НАЧ
3
НАЧ
©
;
1
3
г
НАЧ
3
НАЧ
7
/
!
3
г
НАЧ
3
8.8. Пересечения прямоугольников
451
Заметим, что операции разбиения и слияния заключаются просто в модификации указателей и использовании дополнительной памяти для промежуточных данных. Чтобы проанализировать работу предложенного метода, заметим:
(1) Вся работа ведется на одной и той же памяти с использованием массивов ЧПС и сводится лишь к преобразованиям указателей. Поэтому используемая память равна в (/V).
(2) Что касается времени работы, то каждая пара доминирования (т. е. каждая пара прямоугольников, один из которых охватывает другой) обнаруживается только один раз и за константное время в цикле типа while (строки 7—9) процедуры ОБЪЕДИНЕНИЕ. Поэтому, если S —число таких пар, то на данную работу уйдет оптимальное время Q(S). Остальное затраченное время зависит только от N— мощности множества S; обозначим его через D(N). Обозначим через Md(r,s) время работы алгоритма СЛИЯНИЯ ДОМИНИРОВАНИЙ на паре множеств, состоящих из г и s d-мерных точек, где d = 2, 3. Предполагая для простоты, что N четно, имеем
где O(N) времени займет шаг Д1 — «разделение». Аналогично имеем (полагая, что |S2i| = m, а г —четно)
где 0(r + s)— это опять время, нужное для реализации разбиения множества. Верхняя оценка для M3(r,s) получается в результате максимизации правой части (8.9) относительно параметра т. Поскольку верхней оценкой для M2(r',s/) является 0(r' + s'), то повторяя рассуждения из работы [Kung, Luccio, Preparata (1975)], получаем M3(r, s) = 0((г + s)\og(r + s)), и, следовательно, D(N)= 0(N\og2N).
Тем самым доказана следующая теорема:
Теорема 8.10. Задача об охватах, поставленная на N прямоугольниках (и эквивалентная ей задача о ДОМИНИРОВАНИИ в четырехмерном пространстве), может быть решена за время 0(N log2 N + s) с оптимальной затратой памяти 0(/V), где s — это число пар объектов, связанных отношением доминирования.
Безусловно, остается открытым вопрос о существовании лучшего алгоритма для решения двух вышеупомянутых эквивалентных задач. Вместе с тем установление для них в качестве нижней оценки по времени Q(N\og2 N) является весьма маловероятной перспективой.
D (N) = 2D {NJ2) + М3 (N12, N/2) +0(N),
(8.8)
М3 (г, s) = М3 (г/2, пг) + М3 (r/2, s-m) + + М2 (r/2, max (m, s — m))+0(r + s),
(8.9)
15»
452
Гл. 8. Геометрия прямоугольников
8.9. Замечания и комментарии
Некоторые из задач, обсуждавшихся в данной главе, допускают интересные обобщения. Например, задачу о перечислении пересечений N прямоугольников на плоскости можно обобщить на произвольное число измерений. Обозначим через К число пересекающихся пар гиперпрямоугольников, а через d число измерений. Сикс и Вуд [Six, Wood (1982)] построили алгоритм с оценками О (N logd_1 N 4- К) — по времени и 0(AMogd-'Л7) — по памяти; оценка этого алгоритма по времени позднее была улучшена Эдельсбруннером [Edelsbrunner (1983)] до О (N logd~2 N). Чазелле и Инчерпи [Chazelle, Incerpi (1983)], а также Эдельсбруннер и Овермарс [Edelsbrunner, Overmars (1985)] снизили оценку по памяти до 8(ЛГ), которая, очевидно, является оптимальной, сохранив прежнюю оценку по времени. Соответствующую задачу подсчета в отличие от случая пересечения отрезков (см. разд. 7.2.3) можно решить за время О (N logd~1 N) с затратой О (N logd~2 N) памяти, слегка модифицировав алгоритм перечисления пересечений, принадлежащий Сиксу и Вуду, в то время как алгоритм Чазелле и Инчерпи нельзя адаптировать для эффективного решения данной задачи.
Интересным обобщением задачи о пересечении прямоугольников является задача, обычно называемая ПОИСК ПЕРЕСЕЧЕНИИ С ОРТОГОНАЛЬНЫМИ ОБЪЕКТАМИ, в которой среди заданных N изотетичных объектов надо найти все объекты, которые пересекают заданный, изотетичный им запросный объект. (Разумеется, что канонической формой изотетичного объекта в Ed является декартово произведение d интервалов, каждый из которых может вырождаться в единственное значение. Например, точка, изотетичный прямоугольник, а также горизонтальный и вертикальный отрезки прямых являются ортогональными объектами.) Примером подобной задачи, обсуждавшимся в гл. 2, является многомерный региональный поиск в обеих своих формах: «отчета» и «подсчета». ОБРАТНАЯ ЗАДАЧА РЕГИОНАЛЬНОГО ПОИСКА или ОХВАТА ТОЧКИ также относится к этому классу; она ставится так: среди заданных N изотетичных прямоугольников надо найти такие, которые охватывают некую запросную точку. Вайшнави
[Vaishnavi (1982)] предложил структуру данных, которая обеспечивает поиск с затратами О (log N 4- К)х) времени на один запрос и 0(N\ogN) памяти. Чазелле [Chazelle (1983с)] создал оптимальный алгоритм для этой задачи, т. е. его оценки равны
9(Л0 — по памяти и 9(logN 4- К)— по времени запроса. Еще
') Здесь, как обычно, К обозначает мощность результата. — Прим. перев.
