Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
procedure ПОИСКА, ?); begin 1Щи)=вертикаль) then [I,r]:=[x1,x2] else [1,г}:=[У1,у2}; if((<M(o)<r) then if(P(i>) е= D) then U<=P{v); if(o Ф лист) then
begin \\{l<M{v)) then ПОИСК(ЛСЫН[о],?); if(M{v) < r) then ПОИСК(ПСЫН[о], D)
end
end.
На рис. 2.28(a) показан пример регионального поиска для файла, приведенного на рис. 2.27(a). В частности, на рис. 2.28(b) показан обход узлов Т, осуществленный описанной выше процедурой поиска. Заметим, что только в тех узлах, где поисковый обход раздваивается (таких, как р6, Рг, рг, Pi, рю, Pi, рв), производится проверка принадлежности точки региону. Звездочкой (*) помечены те узлы, в которых такая проверка успешна, и соответствующая точка выбрана. Фактически выбранное множество — это {рз, pi, Ps}-
С точки зрения оценки сложности 2-1>-дерево использует оптимальную память 0(А/) (по узлу на точку из S). Кроме того, его можно построить за оптимальное время 0 (Л/ log N) следующим образом. Вертикальный разрез множества S производится в ре-
') Здесь M(v) = y(P(v)). — Прим. перев. 2) Здесь M(v) = x(P(v)). — Прим. перев.
2.3. Задачи регионального поиске
97
зультате вычисления медианы множества х-координат точек из 5 за время 0(|5|) (с использованием алгоритма из работы [Blum et al. (1973)]) и путем формирования разбиения 5 с такой же оценкой времени; аналогично и для горизонтального разреза. Итак, за время О (N) исходное множество разбивается, в результате чего получаются полуплоскости, в каждой из которых по N/2 точек; тривиально получаем рекуррентное соотношение для времени T(N) работы алгоритма построения дерева: T(N)^2T(N/2) + 0(N),
что и дает обещанную оценку этого времени. В более прямой реализации этого построения обходятся без сложного алгоритма
(а) (Ы
Рис. 2.28. Пример регионального поиска на ранее заданном файле. Часть (Ь) показывает узлы, фактически пройденные при поиске.
поиска медианы. Поскольку в только что описанном методе фактически производится сортировка множеств х- и г/-координат путем рекурсивного поиска медианы, то мы можем прибегнуть к предварительной сортировке для формирования упорядоченных массивов абсцисс и ординат точек из S, именуемых соответственно х- и «/-массивами. Это займет O(NlogN) времени. Первый разрез производится выборкой (за константное время) медианы х-массива путем маркировки тех точек, чьи абсциссы, скажем, меньше этой медианы (за время О (А/)). Маркировка позволяет быстро сформировать два отсортированных подмас-сива, и процесс для них рекуррентно повторяется.
Анализ времени запроса для худшего случая намного более сложен. И не удивительно, что этот анализ был разработан Ли и Вонгом [Lee, Wong (1977)] значительно позже того, как были впервые предложены многомерные двоичные деревья. Очевидно, что время запроса пропорционально общему числу узлов в Т,
4 Зак. 1075
Гл. 2. Геометрический поиск
посещаемых поисковым алгоритмом, поскольку в каждом узле этот алгоритм затрачивает константное время. Очевидно, что это время потрачено в узле v не зря, если точка P(v) выбирает-
Рис. 2.29. Примеры различных типов пересечений D с когда ?>ЛЖ(о)#
ся (продуктивный узел); иначе, этот узел считается непродуктивным. Анализ, проделанный Ли и Вонгом, направлен на построение ситуации худшего случая, т. е. он соответствует максимальному поддереву посещенных узлов, из которых все непродуктивны. Как указано ранее, каждый узел и из Г соответствует
Рис. 2.30. Самовоспроизводящиеся ситуации, соответствующие непродуктивным
некоему обобщенному прямоугольнику 91 (v). Пересечения запросного региона D и подобного обобщенного прямоугольника 9l(v) могут быть отнесены к разным «типам» в зависимости от числа сторон 9l(v), имеющих непустые пересечения с D. В частности, если обозначить это число через i, то говорят, что пересе-
2.3. Эадачи регионального поиска
чение имеет тип i для i = О, 1, 2, 3, 4 (рис. 2.29). Единственный тип пересечений, который всегда продуктивен — это тип 4; все остальные могут оказаться непродуктивными. Ограничимся частными случаями пересечений типа 2 и 3. (Заметим, что пересечения типов 2 и 3 могут начать появляться только на узлах, удаленных от корня на два и три уровня соответственно.) Рассматривая рис. 2.30(a), можно легко построить ситуацию, когда пересечение типа 2 на высоте т непродуктивно и порождает одно пересечение типа 2 и одно пересечение типа 3 на высоте (т— 1) (оба они могут быть сделаны непродуктивными). Аналогично, как показано на рис. 2.30(b), при том же самом ограничении на типы непродуктивных узлов можно построить ситуацию, когда одно пересечение типа 3 на высоте т в Т порождает пару пересечений типа 3 на высоте (т — 2). Итак, обозначая через Ui(m) число пройденных непродуктивных узлов в поддереве высотой т, чей корень имеет тип i (i = 2, 3), получаем рекуррентные соотношения:
U2(m) = U2(m-l) + U3(m-\) + 1, U3(m) = 2U3(m- 2) + 3. Результат же таков: для U2(m) и U3(m) оценка одинакова —
o(VJv).
Заключаем, что для файла мощности N в худшем случае время запроса составит 0(-\/N), даже если выбранное множество окажется пустым. Этот негативный результат для худшего случая противоречит хорошей оценке, полученной методом имитационного моделирования [Bentley (1975)] и подтвержденной эвристическим рассуждением [Bentley, Stanat (1975)].
