Перечисление точек в произвольном прямоугольнике за n * log ^(d - 1) n (range tree)

Конспект готов к прочтению.

Рассмотрим задачу хранения множества точек d-мерного пространства с возможностью перечисления точек, содержащихся в d-мерном прямоугольнике запроса. Эту задачу решает range-tree.

Постановка задачи

Пусть дано пространство [math]X[/math], являющееся произведением [math]d[/math] линейных порядков: [math]X = X_1 \times X_2 \times \dotsm \times X_d[/math].

Отрезком в линейно упорядоченном множестве называется множество [math][a, b] = \{x | a \leq x \leq b\}[/math].

Прямоугольником в пространстве [math]X[/math] назовем произведение отрезков из [math]X_1 \dotso X_d[/math]: [math]I = [a_1, b_1] \times [a_2, b_2] \times \dotsm \times [a_d, b_d][/math], где [math]a_i, b_i \in X_i[/math].

Задача состоит в построении динамической структуры данных, хранящей точки пространства [math]X[/math] и способной эффективно отвечать на запросы по перечислению множества точек, лежащих внутри прямоугольника запроса.

Одномерный случай

Для начала рассмотрим задачу в случае [math]d = 1[/math].

Заметим, что в этом случае точками пространства являются просто элементы некого линейного порядка.

Будем использовать сбалансированное бинарное дерево поиска, в листьях которого будем хранить точки искомого множества, а в нелистовых вершинах - разделющие значения, по которым будет вестись поиск в дереве.

Запрос задачи в одномерном случае превращается в перечисление множества значений, лежащих в отрезке запроса [math][a, b][/math].

Алгоритм, перечисляющий элементы дерева, входящие в отрезок запроса:

• Запустить обычный поиск в двоичном дереве элементов [math]a[/math] и [math]b[/math], остановившись в последней общей вершине пути из корня; назовем эту вершину [math]v[/math].
• Продолжить поиск элемента [math]a[/math] из вершины [math]v[/math]. При этом при каждом переходе к левому ребенку добавлять правое поддерево текущей вершины к ответу. Проверить последнюю вершину (лист) на вхождение в отрезок запроса и в случае необходимости добавить лист в ответ.
• Аналогично, продолжить поиск элемента [math]b[/math] из вершины [math]v[/math]. При каждом переходе к правому ребенку добавлять левое поддерево к ответу. Аналогично проверить последнюю вершину в пути.

Здесь "добавить поддерево к ответу" означает пройти по поддереву целиком и каждый лист добавить к ответу.

Несложно понять, что описанный алгоритм действительно решает поставленную задачу за время [math]O(\log n + k)[/math], где [math]n[/math] - количество элементов в дереве, [math]k[/math] - размер ответа.

Многомерный случай

Теперь рассмотрим общий, многомерный случай задачи. Для её решения будем использовать структуру данных под названием range-tree.

Дадим следующее рекурсивное определение range-tree:

• Одномерное range-tree — просто дерево поиска, описанное выше.
• [math]d[/math]-мерное range-tree — дерево поиска (по первой координате [math]X_1[/math]), аналогичное описанному выше, но в каждой вершине дополнительно хранящее [math]d-1[/math]-мерное range-tree (по остальным координатам [math]X_2 \times \dotsm \times X_d[/math]) для множества элементов, являющихся листами поддерева этой вершины.

Запрос на выдачу точек, принадлежащих некому прямоугольнику, выполняется следующим образом:

• Выполнить описанную выше процедуру поиска элементов отрезка для проекции прямоугольника запроса на [math]X_1[/math].
• При добавлении поддерева к ответу:
  • Если текущая координата - последняя, выдать все листы поддерева в качестве ответа
  • Если текущая координата - не последняя, перейти к сохраненному в корне поддерева range-tree по следующим координатам и повторить тот же алгоритм.

Таким образом, алгоритм сначала найдет по первой координате некоторый набор поддеревьев, потом выполнит поиск по второй координате внутри этих поддеревьев, и так далее.

Оценка времени работы и потребляемой памяти

Фаза алгоритма, обрабатывающая одну координату, может выдать [math]O(\log n)[/math] поддеревьев высотой [math]O(\log n)[/math], каждое из которых будет обработано фазой по следующей координате, и т.д. Таким образом, время запроса - [math]O(\log^d n + k)[/math], где k - размер ответа (количество точек ответа).

Докажем по индукции оценку в [math]O(n \log^{d-1} n)[/math] для потребляемой памяти для структуры range-tree.

[math]d = 1[/math]: в одномерном случае range-tree является обычным деревом, оценка в [math]O(n \log^0 n) = O(n)[/math] очевидна.

[math]d \gt 1[/math]: очевидно, что основным слагаемым в оценке потребляемой памяти будут не сами хранимые элементы, а range-tree меньшей размерности, хранимые в каждой вершине, которые по индукционному предположению занимают [math]O(n \log^{d-2} n)[/math] памяти. Просуммируем размеры этих range-tree (суммирование по расстоянию до вершины от корня): [math]\sum_{k=1}^{\log n} 2^k O(\frac{n}{2^k} \log^{d-2} \frac{n}{2^k}) = \sum_{k=1}^{\log n} O(n \log^{d-2} n) = O(n \log^{d-1} n)[/math]. QED.

Fractional cascading

Техника fractional cascading позволяет снизить ассимптотику запроса в range-tree до [math]O(\log^{d - 1} n + k)[/math].

Упорядоченные последовательности

Рассмотрим две упорядоченных последовательности [math]S_1[/math] и [math]S_2[/math], причем [math]S_2 \subset S_1[/math]. Пусть стоит задача выдать элементы некоторого отрезка, принадлежащие этим последовательностям. Очевидно, это можно сделать бинпоиском для каждой последовательности отдельно за [math]O(\log n + k)[/math], где [math]k[/math] - размер ответа; тем не менее, это решение никак не использует тот факт, что [math]S_2 \subset S_1[/math].

Теперь, зная, что [math]S_2 \subset S_1[/math], для каждого элемента [math]a_1 \in S_1[/math] будем хранить ссылку на минимальный элемент [math]a_2 \in S_2[/math], такой, что [math]a_2 \geq a_1[/math]. В таком случае мы можем избавитсья от двоичного поиске по [math]S_2[/math]: после поиска по [math]S_1[/math], мы можем перейти по ссылке, запомненной для первого элемента ответа из [math]S_1[/math], и выдавать элементы из [math]S_2[/math], пока они лежат в отрезке запроса. Таким образом, запрос для второй последовательности может быть осуществлен за [math]O(1 + k)[/math].

Layered range-tree

Попытался передать как можно подробнее. В любом случае советую почитать еще и де Берга на эту тему.

Не лишним будет разобраться сначала, скажем, со случаем d=2, он наиболее прост и нагляден.

Рассмотрим d-мерное range-tree и запрос, выполненный до [math](d-1)[/math]-ой координаты. На последнем шаге мы выбрали набор вершин, поддеревья которых будут обработаны следующим шагом алгоритма (уже по последней координате). Всегда существует поддерево, содержащее в себе все эти вершины (корнем этого поддерева будет последняя общая вершина в путях от корня дерева к левому и правому концам отрезка запроса). Корень этого поддерева назовем [math]v_{split}[/math].

Вместо хранения деревьев, мы будем хранить массивы вершин, отсортированные по последней координате. Заметим, что множества вершин, соответствующие правому и левому детям некоторой вершины, являются подмножествами множества вершин, соответствующему их родителю. Используем этот факт, чтобы применить fractional cascading. В массивах вместе с вершинами будем хранить ссылку на минимальный элемент массива в левом ребенке, больший или равный текущему элементу массива; аналогично будем хранить ссылки на элементы массива в правом ребенке текущей вершины. Range-tree с такой оптимизацией называют layered range-tree.

Для осуществления запроса найдем двоичным поиском в массиве, хранящемся в [math]v_{split}[/math], левую границу множества элементов, лежащих в отрезке запроса. Далее, при спуске по дереву (при поиске по предпоследней координате), мы можем поддерживать левую границу текущего поддерева (границу по последней координате), используя сохраненные ссылки. При обработке поддерева по предпоследней координате, используя сохраненный в корне поддерева массив вершин и ссылку на левую границу ответа, мы можем выдать ответ за [math]O(1 + k_v)[/math], где [math]k_v[/math] - размер ответа в поддереве вершины [math]v[/math].

Таким образом, мы избавились от поиска по дереву на последнем уровне range-tree, сократив врем работы до [math]O(\log^{d-1} n + k)[/math].

Ссылки

• van Kreveld, de Berg, Overmars, Cheong — Computational Geometry. Algorithms and Applications. Страницы 105-109, 112-115.