Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Обобщение вышеописанного метода на случай d измерений получается непсредственно. Здесь мы будем работать с секущими гиперплоскостями, ортогональными координатным осям, а все, что необходимо определить, — это критерий, по которому следует выбирать ориентации этих секущих гиперплоскостей. Если координаты обозначены через хи х2, .... ха, то одним из возможных критериев будет циклический сдвиг на последовательности (1, 2, d) индексов координат. Результирующее разбиение е?-мерного пространства моделируется двоичным деревом с N узлами, которое называется многомерным двоичным деревом или k-D-деревом1)- Анализ эффективности также можно обобщить на случай d измерений, однако этого здесь мы делать не будем. Подведем итоги в следующей теореме:
') Выражение «Л-О-дерево» — это принадлежащая Д. Кнуту аббревиатура для «6-мерного дерева двоичного поиска». Оно не слишком выразительно, но уже вошло в современный профессиональный жаргон.
4*
100
Гл. 2. Геометрический поиск
Теорема 2.9. С помощью метода k-D-дерева региональный поиск на d-мерном множестве (при из N точек можно
провести за время 0(dNl-1'd + k) с использованием Q(dN) памяти, если затратить Q(dN log N) времени на предобработку. Поэтому метод k-D-дерева дает (dN, dN[~]/a)-алгоритм.
Оптимальные оценки по памяти и времени предобработки, к сожалению, не компенсируют обескураживающую оценку времени поиска для худшего случая. Поэтому неудивительно, что в качестве альтернатив были предложены другие методы. Эти методы будут описаны ниже.
2.3.3. Метод прямого доступа и его варианты
Неэффективность метода fe-D-дерева для худшего случая является важным мотивом для исследования методов, обладающих удовлетворительными оценками времени поиска, возможно, за счет ухудшения двух других обсуждавшихся оценок эффективности. Мы начнем с самого простого метода, а затем последовательно будем его улучшать.
Как упоминалось в разд. 2.3.1, самый грубый способ минимизации времени поиска состоит в предварительном вычислении ответов на все возможные при региональном поиске запросы. Поэтому возникает искушение заявить, что время поиска можно сократить до 0(1), поскольку единственное обращение к памяти завершило бы поиск. Это, конечно, приводит к постановке головоломного вопроса о кажущемся противоречии с нижней оценкой, полученной в разд. 2.3.1. Скоро мы поймем, что есть одна загвоздка, и все встанет на свои места.
Следуя подходу, введенному в разд. 2.1, предположим, что дано множество S из N точек на плоскости, и проведем горизонтальную и вертикальную прямые через каждую из этих точек. Разумеется, эти прямые разобьют плоскость на (Л/+ I)2 прямоугольных ячеек. Положим, что в регионе D = [xi,x2\'X Xiyi, Ун] точка (хи у{) принадлежит ячейке С\, а точка (х2, у2) — ячейке С2. Если теперь переместить как угодно любую из этих точек, оставляя ее, однако, внутри соответствующей ячейки, то очевидно, что искомое множество (т. е. подмножество 5, содержащееся внутри D) не изменится. Другими словами, пары ячеек формируют классы эквивалентности относительно результатов регионального поиска. Следовательно, число различных регионов, которые нам следовало бы рассмотреть, ограничено сверху числом
{ 2 )Х( 2 h°m-
2.3. Задачи регионального поиска
101
Если предварительно вычислить выбираемое множество для каждой из этих пар ячеек (затратив при этом О (А/5) памяти), то мы получили бы схему, в которой поиск заканчивается после единственного обращения к файлу. Однако для достижения этой цели произвольный регион D нужно сопоставить паре ячеек, или, что то же самое, произвольная точка должна быть сопоставлена одной из ячеек. Очевидно, что это можно проделать двумя двоичными поисками на множествах абсцисс и ординат точек из S. На эту «нормализацию», однако, уйдет О (log Л/) времени, которое, будучи добавленным к 0(1) времени на единственное обращение к файлу, разрешает кажущееся противоречие, встреченное нами ранее. Заметим в заключение, что данный метод дает на плоскости (Л/5, log N)-алгоритм, слишком обременительный для практического использования из-за затрат памяти.
Чтобы найти пути сокращения памяти, заметим, что одномерный поиск, несмотря на наши безуспешные усилия обобщить его, является оптимальным по обеим мерам (времени поиска и памяти). Это замечание заставляет предположить возможность улучшения вышеописанного «метода ячеек». В самом деле, можно объединить одномерный региональный поиск с локализацией региона методом прямого доступа [Bentley, Maurer (1980)]. Конкретно, для заданного региона D = [хи х2]Х1У\, уЦ можно реализовать прямой доступ по координате х с последующим одномерным поиском по координате у. Для этого требуется, чтобы ко всем различимым упорядоченным парам абсцисс точек из S (х-регионы) был обеспечен прямой доступ; каждая такая пара [х\ х") в свою очередь связана с двоичным деревом поиска на ординатах точек, содержащихся в полосе х' ^ х ^ х". Теперь удобно преобразовать исходную задачу, заменяя каждое действительное значение координаты на ее порядковый номер во множестве координат. Такое преобразование, именуемое нормализацией, осуществляется путем операции сортировки на каждом из множеств координат. После нормализации этих данных любой х-регион преобразуется за время О (А/ log N) в пару целых чисел (i, /) из отрезка [1, А/ + 1] (i < /). Такая пара соответствует адресу в массиве указателей прямого доступа'), который отсылает к двоичному дереву с (/ — i) листьями. Поэтому общий объем памяти пропорционален
