Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Рис. 8.30. Пример отнесения множества интервалов в статическом дереве интервалов. Дуги, обозначенные сплошными линиями, образуют первичную структуру; пунктирные дуги образуют вторичные структуры; штрих-пунктирные линии образуют особую сверхструктуру Т.
поддереве узла и, и аналогично ПУ[у]=^Л только тогда, когда существуют активные узлы в правом поддереве v. Заметим, что больше половины активных узлов имеют непустые вторичные списки.
На рис. 8.30 приведен пример отнесения интервалов в статическом дереве интервалов.
Во-первых, рассмотрим вопрос об управлении вставками и удалениями в статическом дереве интервалов. Заметим, что как первичная структура, так и каждый из вторичных списков реализуются посредством двоичных деревьев глубины О (log Л7). Вставка интервала [Ь, е] заключается в проходе пути в Г от корня до первого узла v* такого, что b ^ б (о*) ^ е (развилки); в этот момент ордината b вставляется в 3?(у*), а ордината е — в &(v*). Проверка того, что при этом левые и правые указатели можно поддерживать за константное время в расчете на один узел, является достаточно простым упражнением. По аналогии с незначительными изменениями можно выполнить и удаление. Каждая из этих операций требует время O(logJV).
440
Гл. 8. Геометрия прямоугольников
Теперь проанализируем поиск на интервальном дереве, т. е. определение пересекающихся пар интервалов при вставке интервала [Ь, е\ в Т. Опять пройдем по некоему (возможно, пустому) пути от корня к первичному узлу v* (развилке) такому, что b^.8(v*)^e. Затем, начиная от v*, пройдем по двум разным путям к двум листьям в поддереве с корнем в v*, которые связаны с величинами Ь и е соответственно (рис. 8.31). Пусть
Рис. 8.31. Поиск в интервальном дереве. Закрашенные треугольники обозначают вторичные списки, которые следует обойти. Поименованные поддеревья также необходимо обойти (с помощью ЛУ и ПУ).
Р„ач обозначает последовательность узлов от корня до узла, предшествующего и*; кроме того, пусть Рл — последовательность узлов от v* до листа Ъ, а Р„ — последовательность узлов от v* до е. Рассмотрим два основных случая:
1. t) е РНач. В этом случае [Ь, е] лежит слева или справа от 6(t>). Предположим без потери общности, что е^б(у). Поэтому прежде всего надо проверить возможность пересечения [Ь, е] с какими-нибудь из активных интервалов, содержащих б (у). Для любого такого активного интервала e(i)] эта проверка производится путем выяснения справедливости условий Ь ^ е или ^ Ь sg; е<''>. Но поскольку b < е ^ ^ б (v) <.е(-'\ то характеристическим условием пересечения интервалов [&('), еЩ и [Ь, е] является только =?Г е; оно проверяется путем сканирования 9? (v) в порядке возрастания и перечисления всех тех интервалов, для которых это условие
ftoper
Лист
8.8. Пересечения прямоугольников
441
выполнено. Делается эта работа эффективно за время, пропорциональное числу найденных пересечений (без лишнего поиска).
2. oePj (и аналогично с соответствующими изменениями v ее Рп). Если б (и) ^ Ь, то рассуждая так же, как при v е= РНач, необходимо просмотреть правый список узла v—9l(v) в убывающем порядке (опять без лишней работы). Если же b < <б(о), то известно, что [Ь, е] пересекает не только все активные интервалы, отнесенные к v, но также и все интервалы, отнесенные к узлам из правого поддерева v. Первое из этих множеств получается простым перечислением тех интервалов, чьи правые концы находятся в 9l(v). Второе множество получается в результате обхода активных узлов правого поддерева. Для эффективного решения последней задачи будут использованы дуги, определяемые значениями ЛУ и ПУ. Согласно предыдущим рассуждениям (менее половины активных узлов в этом поддереве имеют пустые вторичные списки), число пройденных узлов по порядку будет равно числу перечисленных интервалов.
Анализ трудоемкости вышеописанного метода не составляет труда. Прежде всего статическое дерево интервалов для набора из N интервалов требует O(N) памяти, поскольку в нем будет 4/V— 1 первичных узлов, и еще не более 2N элементов необходимо запомнить во вторичных списках. Скелетная первичная структура строится за время 0(N\ogN), поскольку необходима предварительная сортировка абсцисс. Каждый интервал вставляется или удаляется за время О (logЛ7), как упоминалось выше. Поиск в дереве требует О (log Л7) времени для прослеживания поисковых путей (см. опять рис. 8.31), хотя на каждый обнаруженный интервал тратится константное время; единственные накладные расходы, относящиеся к соответствующему первичному узлу, пропорциональны числу вторичных списков, обрабатываемых в процессе данной работы. Заметим, кроме того, что если поиск в дереве осуществляется только в связи со вставкой прямоугольника (т. е. при вставке его левой стороны), то каждая пересекающаяся пара будет обнаружена ровно один раз. В заключение подведем итог предыдущему обсуждению следующей теоремой:
Теорема 8.9. Обнаружить s пересекающихся пар в наборе из N изотетичных прямоугольников можно за оптимальное время Q (N log N + s), затратив O(NlogN) времени на предварительную обработку и используя оптимальную память Q(N).
