Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
В частности, при d = 2 эти меры — время запроса, память и время предварительной обработки — выглядят так: 0(log2 N + k), 0{NlogN) и 0{NlogN)1) соответственно. Достигнута весьма привлекательная оценка памяти, хотя и при некотором увеличении времени поиска.
Прежде чем согласиться с таким соотношением оценок, которое, вероятно, внутренне присуще этой задаче, стоит еще раз осмыслить вопрос о возможной потере эффективности процесса поиска. Уиллард [Willard (1978)] и Люкер [Lueker (1978)], именно так и поступив, независимо друг от друга предложили вариант схемы, в которой достигается оптимальное время поиска для двух измерений. Теперь обсудим эту идею.
Каждый узел v в первичном дереве отрезков связан со списком Y(v) (а не с двоичным деревом!) тех точек, которые проецируются на отрезок этого узла. Этот список упорядочен так, чтобы ординаты указанных точек не убывали. Чтобы осуществить выборку, необходимо найти первый элемент подсписка, который надлежит выбрать. В схеме метода дерева регионов с этой целью делается двоичный поиск для каждого узла v из первичного дерева. Если рассмотреть два потомка узла v, мы увидим, что У(ЛСЫЩи]) и У(ПСЫН[и]) образуют разбиение У (и). Предположим, теперь, что р — начальный (крайний слева) элемент Y(v), подлежащий выборке, — известен. Без потери общности положим, что если ре У(ЛСЫН[и]), то существует единственный элемент р' в У(ПСЫН[у]) такой, что у(р') — наименьшее число, для которого у(р) ^ у{р'<)- Следовательно, пара указателей от р к Y(v) однозначно определяет соответствующую пару начальных элементов в У-списках для потомков v.
Теперь относительно просто можно сделать выводы. В дереве регионов можно заменить каждое прошитое двоичное дерево его листовым списком для всех узлов, кроме корня. В качестве же корневой структуры сохранится прошитое двоичное дерево, поскольку оно необходимо для реализации поиска за логарифмическое время. Для каждого нелистового узла в дереве отрезков хранится пара указателей от каждого из элементов его У-списка к паре У-списков его потомков. Этот метод иногда называют расслоением, а модифицированное дерево ре-
') Заметим, что метод дерева регионов можно очевидным образом адаптировать для режима подсчета точек и получить следующие оценки для трех мер сложности: 0(log2yV), 0(N log N) и 0(N log N). Это подтверждает один из результатов, приведенных в разд. 2.1 (табл. I).
2.3. Задачи регионального поиска
109
гионов можно называть расслоенным деревом регионов. Использование модифицированного дерева регионов для случая нашего постоянного примера показано на рис. 2.34.
Затраты памяти не изменились, поскольку и прошитое двоичное дерево с s листьями, и список с s записями и парой внешних указателей на каждую запись требуют по O(s) памяти. Однако время поиска сократилось до O(logjV), поскольку дво-
Рис. 2.34. Иллюстрация обхода модифицированного дерева регионов для нашего постоянного примера. Показана только часть указателей в У-списках.
ичный поиск в корне осуществляет начальную локализацию левого конца «/-региона. Эта структура указателей реализует за константное время вычисление левого конца для каждого узла, встреченного при «проходе» дерева отрезков. При обобщении этой схемы на случай большего числа измерений сохраняется эффект уменьшения оценки времени поиска в log N раз. Итак, получаем:
Теорема 2.12. Региональный поиск в d-мерном файле (при d ^ 2) из N точек можно реализовать (N logd_1 N, logd_1 N)-алгоритмом, если затратить (N logd_1 N) времени на предварительную обработку. Этот алгоритм основан на модификации алгоритма Уилларда— Люкера для дерева регионов, известной также как расслоенное дерево регионов.
по
Гл. 2. Геометрический поиск
2.4. Замечания и комментарии
Со времени появления статьи Добкина и Липтона был достигнут заметный прогресс в решении задачи о локализации точки. Как указывалось в разд. 2.2, все представленные методы формируют новые геометрические объекты, помогающие при поиске. Например, в методе полос плоскость разбивается на элементарные пустые трапеции, обладающие парой горизонтальных сторон; два этапа двоичного поиска определяют одну-единственную трапецию. В методе детализации триангуляции путем перетриангуляции частей ППЛГ создается удобное малое множество новых треугольников, на котором легко проводить поиск. В методе трапеций ведется эффективное обследование исходного графа путем создания трапеций, обладающих парой горизонтальных сторон, которые быстро сужают область поиска. Наконец, в методе цепей из плоского прямолинейного графа выделяется множество цепей ломаных линий, разбивающих плоскость на монотонные многоугольники, на которых легко вести поиск. Хотя этот метод почти оптимален, его можно улучшить и получить оптимальный и при том весьма простой алгоритм: это улучшение основано на удачном сочетании метода цепей, структуры указателей Уилларда — Люкера и «фильтрующего поиска». Ниже будет кратко описан фильтрующий поиск.
Фильтрующий поиск [Chazelle (1983с)]') это один из общих методов решения задач поиска в режиме отчета, основанный на вычислительно разумной идее о том, что можно позволить доступ к супермножеству искомого множества, если при этом получается выигрыш вычислительных ресурсов (таких как память или время поиска), при условии что мощность супермножества превосходит не более чем заданную (малую) мультипликативную константу — мощность искомого множества. Другими словами, это супермножество является «черпаком», который выбирают, а затем «фильтруют», чтобы выделить искомое множество; поэтому «фильтрующий поиск» можно не без оснований называть поиском типа «черпай и фильтруй». Этот подход был успешно применен к различным задачам, таким как запросы с ортогональным регионом, поиск близости (см. гл. 6), к задачам пересечения и т. д.
