Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Тл i t+i{i ~~0 = [{N +1)3 ~(N +1 )]/6 = 0 т'
. ') Например, если этот массив начинается с адреса А, то по паре (»,/) можно однозначно вычислить адрес: А — 2 +{2N{i —!)+« — /г)/2 + /•
102
Г л. 2. Геометрический поиск
.Pi
•Р9.Р„
wMm
Ш
> у- регион Psj -Р'°
PsS *-x-peeuw*-
(а)
^^Произвольный доступ
I ?1 П
х - массив
Рис. 2.31. Региональный поиск прямым доступом. Адрес ^-интервала локализуется методом произвольного доступа после нормализации. По этому адресу находится указатель к двоичному дереву поиска.
Заметим, что, хотя память удалось сократить с О (А/5) до О (Л/3), время поиска осталось равным О (log Л/), поскольку и нормализация регионов, и одномерный региональный поиск используют 0(logA/) времени. Ситуация, характерная для последнего примера, проиллюстрирована на рис. 2.31 (заметим, что точки индексированы в порядке возрастания абсцисс). В массиве х имеется доступ к региону [2, 8], заданному нормализованными абсциссами (рис. 2.31(b)); отсюда указатель направляет поиск к двоичному дереву. Там поиск, как таковой, заканчивается лока-
2.3. Задачи регионального поиска
лизацией точки Р«, после чего производится выборка последовательности (Ре, Рз, Pi)-
У нас все еще мало оснований, чтобы быть довольными вышеописанным методом, и не только потому, что затрата О (Л/3) памяти остается весьма дорогой платой, но также потому, что в многомерном случае трюк с использованием одномерного поиска можно проделать лишь однажды, тем самым снижая используемую память только в Л/2 раз. И на самом деле непо-
,1 j Регион, который. ' 1 надо локализовать
рис. 2.32. пример двухэтапной схемы метода прямого доступа.
средственный анализ показывает, что если этот подход обобщить на случай d измерений, то будет использовано 0(N2d~l) памяти.
Очевидно, что именно фаза прямого доступа в этой двухфазной схеме виновна в большой затрате памяти. Поэтому улучшения нужно искать именно в этой фазе. Бентли и Маурер предложили многоэтапный подход [Bentley, Maurer (1980)] '), который будет продемонстрирован здесь для случая двух этапов. Идея состоит в том, чтобы последовательно использовать грубую сетку и мелкую сетку (рис. 2.32). Все координаты нормализуются, и грубая сетка состоит из отрезков длиной k, при этом на каждом таком отрезке существует мелкая сетка, состоящая из отрезков единичной длины. Отсюда видно, что произвольный регион разбивается не более чем на три части, одна из которых целиком принадлежит грубой сетке, а две других — мелкой сетке (рис.2.32). Каждой сетке соответствует описанный выше массив указателей прямого доступа. В частности, если грубая сетка состоит из Na шагов (0<а^1), то на грубой сетке всего будет 0(N2a) отрезков, а для соответствующей структуры данных потребуется 0(N2a) ХЛ/ = 0(Л/1+2а) памяти. Аналогично каждая мелкая сетка состоит из Л/1_а шагов и всего будет Na таких сеток, поэтому общая память для них составит величину порядка Na X М1-"'2 X ^I_a = N3~2a. Минимального значения, равного 0(N2), память достигает при a = 1/2 без
') структуры данных, которые будут введены, первоначально назывались многоуровневыми fe-регионами.
104
Г л. 2. Геометрический поиск
потери логарифмической оценки для времени регионального поиска. Фактически время поиска возрастает примерно в 3 раза, и мы получаем 0(N2, log N) -алгоритм.
Теперь можно обобщить этот подход, используя последовательность из / сеток возрастающей мелкости, для дальнейшего сокращения памяти при сохранении, однако, оценки времени поиска в пределах О (/log Л'). Этот относительно простой анализ приводит к следующей теореме:
Теорема 2.10. Для любого е такого, что 0 < е < 1, региональный поиск на двумерном N-точечном файле можно провести с помощью (Nl+E, log N) -алгоритма, основанного на многоэтапном методе прямого доступа.
Самый интересный вывод, который можно извлечь из предшествовавшего обсуждения методов прямого доступа, состоит в следующем. Одномерный региональный поиск можно сделать оптимальным. Поэтому следует добиваться преобразования многомерной задачи в серию одномерных задач. Схема прямого доступа — это один из путей реализации такого преобразования. В принципе в двумерном случае произвольный отрезок разбивается на не более чем три стандартных отрезка (и в cf-мерном случае точно так же в конечном итоге получается некое фиксированное число стандартных отрезков). Данный подход содержит в себе некоторые идеи метода дерева регионов, который будет описан ниже ').
2.3.4. Метод дерева регионов и его варианты
Эффективность по времени поиска в методе прямого доступа получена благодаря построению набора «стандартных» отрезков. Выигрыш в памяти при переходе от одноэтапной схемы к двухэтапной получен благодаря сильному сокращению числа таких стандартных отрезков. Возникает стремление к дальнейшему следованию этой линии, т. е. к созданию схемы, минимизирующей число стандартных отрезков. В этом и состоит главная идея метода регионального дерева.
Рассмотрим множество на оси х, состоящее из N абсцисс, нормализованных до целых чисел из интервала [1, ./V] по их величине. Эти N абсцисс определяют N—1 элементарных отрезков [/, /+ 1] для [' = 1, 2, ..., N— 1. Средством, которое будет
