Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
') Однако хронологически метод дерева регионов был создан немного ранее методов прямого доступа [Bentley (1979)]. Тем не менее с чисто идейной стороны его можно считать развитием последних методов. Первые идеи, связанные с понятием дерева регионов, можно найти в работе [Bentley, Shamos (1977)].
2.3. Задачи регионального поиска
105
использовано для реализации разбиения произвольного отрезка /], является дерево отрезков, введенное в разд. 1.2.3.1. Повторим просто для удобства читателя, что произвольный отрезок, концы которого принадлежат множеству из N заданных абсцисс, может быть разбит деревом отрезков 7(1, N) на не более 2riog2A/"| — 2 стандартных отрезков. Каждый стандартный отрезок отнесен к одному из узлов 7(1, N), а те узлы, которые определяют разбиение отрезка [i, j], называются узлами отнесения для [i, /].
После такого напоминания не составит труда воспользоваться деревом отрезков при региональном поиске. Начнем, как обычно, с двумерного случая. Дерево отрезков 7(1, N) используется при поиске по дг-координате. Этот поиск определяет уникальное множество узлов (узлов отнесения). Каждый такой узел v соответствует множеству из (E[v] — B[v]) абсцисс (определения даны в разд. 1.3.2.1), т.е. множеству из (E[v] —B[v]) точек на плоскости. Ординаты этих точек образуют обычное прошитое двоичное дерево для регионального поиска в «/-направлении. В результате построена новая структура данных, именуемая деревом регионов; его первичной структурой является дерево отрезков, заданных на абсциссах точек исходного множества S. В каждом узле этого дерева имеется указатель на прошитое двоичное дерево поиска (вторичные структуры). Для нашего постоянного примера эта структура проиллюстрирована на рис. 2.33.
Обобщение на d измерений можно провести весьма естественно. Пусть в rf-мерном пространстве с координатными осями Х\, Xq, ..., xd задано множество S из JV точек. Эти координаты будут обрабатываться в следующем порядке: сначала х\, затем х2 и т. д. Предположим также, что все значения координат нормализованы. Дерево регионов строится рекурсивно следующим образом:
(1) Первичное дерево отрезков 7* соответствует множеству {х\(р)\ peS). Для каждого узла v из 7* обозначим через Sd (v) — множество точек из 5, проецирующихся на отрезок [B[v], E[v]) по координате Хи Определим (d — 1)-мерное множество:
Sd^'(v)A {(х2(р), .... xd(p)): p^Sd(v)}.
(2) Узел v из 7* имеет указатель на дерево регионов для Sd-i(v).
Перед тем как приступить к анализу эффективности данного метода, заметим, что дерево отрезков можно считать не только инструментом для разбиения любого отрезка на логарифмическое число кусков, но также и способом применения метода «разделяй и властвуй» к региональному поиску.
106
Г л. 2. Геометрический поиск
2.3. Задачи регионального поиска
107
ности, узел v порождает поиск на п (v) Д Е [v] — В [v] точках. Обозначая через Q(N, d) время поиска для файла из N штук d-мерных точек, получаем простое рекуррентное соотношение:
Q (N, d) — 0 (log N) + иемножЕтву узлов Q (" (»), d - 1). (2.4)
запросного региона
Первый член в правой части этого уравнения появился из-за поиска на первичном дереве отрезков, а второй член объясняется наличием (d—1)-мерных подзадач. Поскольку существует не более 2Tlog2Л/"1 — 2 узлов отнесения и n(v)^N (очевидно), то получаем
Q(N, d) = О (log N)Q(N, d- 1).
Поскольку Q(N, 1) = О (log N) для двоичного поиска, то получаем оценку времени поиска:
Q (Л/, d) = 0 ((log N)d). (2.5)
Обозначая через S(N, d) память, занятую деревом регионов, получаем рекуррентное соотношение
S(N, d) = 0(N)-\- Z S(n(v), d-l), (2.6)
по всем узлам о первичного дерева
где первый член в правой части соответствует памяти, занятой первичным деревом, а второй член соответствует всем (d— 1)-мерным деревьям. Оценка второго члена очень проста, если JV есть степень 2; в противном случае будет использована столь же эффективная простая аппроксимация. Существует не более двух узлов v с n(v) — 2rlogjJVl"1) не более четырех — cn(v) = 2rloBlJVl""2 и т. д. Поэтому эту сумму можно оценить сверху следующим образом:
Е S(n(v), d—1)< S 2n°g^-i-<.s(2', d- 1).
по всем узлам о i=0
первичного дерева
Учитывая эту аппроксимацию и замечая, что 5 (Л/, 1)= О(N) — память под прошитое двоичное дерево, получаем решение S (N, d) = 0(N log*-1 N). (2.7)
Для оценки времени предварительной обработки можно следовать той же самой схеме рассуждений; оставим это в качестве весьма простого упражнения. В самом деле, в этом случае для оценки эффективности применимо рекуррентное соотношение, идентичное (2.6), со всеми его следствиями. Теперь можно подвести итог предшествовавшему обсуждению в следующей теореме:
108
Гл. 2. Геометрический поиск
Теорема 2.11. Региональный поиск на d-мерном файле из N точек можно провести (Л/logd-'N, logd N)-алгоритмом, если затратить 0(N logd_1 N) времени на предварительную обработку. Этот алгоритм основан на методе дерева регионов.
