Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Гл. 2. Геометрический поиск
главы '). Итак, в общем случае верхняя оценка времени запроса в режиме отчета будет выражена в форме 0(f(N, d) + k-g(N, d)); эти два слагаемых следует понимать как соответственно «время поиска» и «время выборки», если допустимо в точности выбираемое множество, или как времена запроса для «малого» (k= = О (ДА/, d))) и «большого» (f{N,d) = o{k)) выбираемых множеств в более общем случае.
Относительно нижних оценок сразу же заметим, что Q(k) — это тривиальная нижняя оценка времени выборки, поскольку длина результата пропорциональна k. Что же касается времени поиска, то обратимся к модели дво-*а Типичный ичного дерева решений, которая, [ Janpcm как хоР°шо известно, подсчиты-
I ; I вает число сравнений, необходи-
—»« » !»« —-»!-«-мых для доступа к элементам мно-
~а | ~!',' 1 \ а жества S'c^S внутри запросного
\ i региона (заметим, что здесь мы
' считаем доступными только те эле-
~а менты, которые необходимо вы-
брать). Это число сравнений огра-Рис. 2Ж Пример множества ничено снизу величиной log2Q(5), при а — 2. где q ^ _ число разЛИЧНых подмно-
жеств S, получаемых как ответы на запросы. Обращаясь к рис. 2.26, рассмотрим следующее множество [Bentley, Maurer (1980)]: S — множество всех точек, имеющих одну и только одну ненулевую целочисленную координату в интервале [—а, а]; ясно, что N = 2ad. Затем выберем независимо по каждой оси координат два любых целых числа в интервалах соответственно {—а, —1] и [1, а]; они и определят регион запроса, для которого подмножество связанных с ним точек непусто и отлично от всех других подмножеств. Поскольку вышеупомянутый выбор можно осуществить a2d = (NI (2d))2d способами, то нижняя оценка числа двоичных решений равна Q(\og(N/(2d))2d) = Q(d\ogN). Хотя более тонкий комбинаторный анализ [Saxe (1979)] может дать более точную оценку числа ортогональных регионов, обладающих различными выбираемыми множествами точек, однако и простые доводы, приведенные выше, дали нам нижнюю оценку времени поиска Q(d\ogN). К сожалению, как отметил Люкер [Lueker (1978)], модель де-
') Существует принципиальное отличие фильтрующего поиска от того метода поиска, в котором заданный регион аппроксимируется регионами других типов (например, сферический регион — гиперпрямоугольными). Хотя оба эти метода не относятся к типу «точного доступа», при фильтрующем поиске размер доступного множества не более чем на мультипликативную константу отличается от размера выбираемого множества.
2.3. Задачи регионального поиска
рева решений, по-видимому, не адекватна для данной задачи, поскольку для больших d все известные методы показывают экспоненциальную, а не линейную зависимость времени поиска от d (т.е. верхняя граница имеет вид О ((log N)d)). Этот вопрос был поставлен Фредменом [Fredman (1981)], который доказал нижнюю оценку времени поиска Q((logA/)d) для динамических запросных систем (оценивая сложность операции «*» на полугруппе, которая была введена ранее в настоящем разделе); однако не совсем ясно, как результат Фредмена можно приложить к рассматриваемой здесь ситуации. Наконец, заметим, что Q(Nd)—тривиальная нижняя оценка памяти, занятой под структуру данных поиска.
Остаток этой главы будет посвящен в основном алгоритмам для задачи типа «отчета», а не типа «подсчета» (за иключением упражнения 4). Заметим, что алгоритм первого типа можно тривиально использовать для решения задачи второго типа; однако обратное преобразование в общем случае невозможно, т. е. могут быть развиты специфические эффективные методы для решения задачи типа «подсчета». Для всех описываемых алгоритмов время поиска выражается в форме 0(f(N,d) + k).
В следующих разделах показано несколько достаточно интересных и тонких методов, предложенных для задачи регионального поиска. Будет пролит свет на те трудности, которые до сих пор не позволяют построить оптимальные алгоритмы и которые непосредственно определяют соотношение между двумя важными ресурсами — временем запроса и объемом памяти.
Чтобы соответствующим образом подготовиться к изложению существующих методов, нам придется начать с простейшего примера регионального поиска, который при совершенной своей тривиальности содержит существенные черты данной задачи: речь пойдет об одномерном региональном поиске.
Множество из N точек на оси х представляет файл, а запросным регионом является отрезок [х',х"] (называемый х-регио-ном). Методом, дающим эффективный (оптимальный) региональный поиск, является двоичный поиск, т. е. дихотомия искомого упорядоченного множества. В самом деле, ясно, что х' — левый конец х-региона — локализуется на оси х дихотомией; на этом завершается поиск, а для осуществления выборки надо пройти ось х в направлении вырастания х вплоть до достижения правого конца х". Структурой данных, обеспечивающей указанное действие, является прошитое двоичное дерево, т. е. такое сбалансированное двоичное дерево, листья которого дополнительно связаны в списке, отражающем порядок абсцисс; дерево и список обрабатываются на фазах соответственно поиска и выборки. Заметим, что описанный метод оптимален как по времени запроса 9(logA7 + k), так и по памяти 6(Л7).
