Дерево интервалов (interval tree) и пересечение точки с множеством интервалов

2014-02-22T10:49:27Z

217.118.78.97: /* Псевдокод */

[[Категория: Вычислительная геометрия]]
== Определение ==
Дерево интервалов (interval tree) позволяет решать следующую задачу. Дано множество отрезков <tex>I=\{[x_1, x'_1], \ldots, [x_n, x'_n]\}</tex> и множество запросов. Каждый запрос характеризуется точкой <tex>q_x</tex>. Для каждого запроса необходимо определить множество отрезков из <tex>I</tex>, которые содержат в себе <tex>q_x</tex>. Построение дерева интервалов занимает время <tex>O(n \log\,n)</tex>, а также <tex>O(n)</tex> памяти. На каждый запрос дерево интервалов позволяет отвечать за <tex>O(\log\,n + k)</tex>, где <tex>k</tex> {{---}} размер ответа на запрос.
== Построение ==
Чтобы построить дерево интервалов сделаем следующее. Найдем медиану множества всех координат отрезков <tex>x_{mid}</tex>. Это можно сделать за <tex>O(n)</tex> (см. [[Поиск k-ой порядковой статистики за линейное_время | Поиск k-ой порядковой статистики]]). Далее разделим все отрезки на три группы: те, которые лежат строго слева (справа) от <tex>x_{mid}</tex> и все остальные. Для первых двух групп рекурсивно построим дерево интервалов. Все остальные отрезки будем хранить в корне дерева. Создадим два списка отрезков, которые пересекают <tex>x_{mid}</tex>. В одном отсортируем их по левой координате, в другом {{---}} по правой.
{{Теорема
|statement=
Дерево интервалов имеет глубину <tex>O(\log\,n)</tex>.
|proof=
При каждом рекурсивном вызове построения дерева множество концов отрезков уменьшается более чем в два раза. Значит, после <tex>O(\log\,n)</tex> рекурсивных вызовов, множество отрезков будет пусто.
}}
{{Теорема
|statement=
Дерево интервалов занимает <tex>O(n)</tex> памяти.
|proof=
По построению каждый отрезок был добавлен ровно в два списка. Вершин в двоичном дереве глубины <tex>O(\log\,n)</tex>, очевидно, <tex>O(n)</tex>.
}}
{{Теорема
|statement=
Построение дерева интервалов работает за <tex>O(n\log\,n)</tex> времени.
|proof=
Отдельно оценим время, которое необходимо для создания всех отсортированных списков отрезков. Т. к. их суммарная длина <tex>O(n)</tex>, требуется <tex>O(n\log\,n)</tex> времени. Теперь рассмотрим время, необходимое для рекурсивных вызовов. Для каждой вершины дерева это время равно <tex>O(m)</tex>, где <tex>m</tex> {{---}} количество отрезков, которые были переданы рекурсивно. Просуммируем это время по всем <tex>O(\log\,n)</tex> "слоям" дерева. Под каждым слоем понимаются все вершины дерева, которые лежат на одной и той же глубине. Т. к. в каждом слое множества отрезков для любых двух вершин не пересекаются, то суммарное количество отрезков в слое равно <tex>O(n)</tex>. Слоев всего <tex>O(\log\,n)</tex>, значит, имеем общую оценку <tex>O(n\log\,n)</tex> для построения всего дерева.
}}

== Как отвечать на запрос? ==
В каждой вершине дерева хранится <tex>x_{mid}</tex>, ссылки на два поддерева, а также два отсортированных списка отрезков. В вершине хранятся только те отрезки, которые пересекают <tex>x_{mid}</tex>. Необходимо рассмотреть два симметричных случая. Покажем, что делать в одном из них. Пусть, например, <tex>q_x>x_{mid}</tex>. Тогда в ответ нужно добавить некоторый суффикс отрезков, которые отсортированы по правому концу. Запустимся рекурсивно от правого дерева (т. к. понятно, что никакой отрезок, который хранится в левом поддереве не может содержать <tex>q_x</tex>). Аналогично разбирается случай <tex>q_x < x_{mid}</tex>.
{{Теорема
|statement=
Ответ на запрос происходит за <tex>O(\log\,n + answer)</tex> времени.
|proof=
Глубина дерева равна <tex>O(\log\,n)</tex>, значит может быть только <tex>O(\log\,n)</tex> рекурсивных вызовов. В каждой вершине ответ происходит за <tex>O(answer)</tex>, т. к. может быть просмотрен только один отрезок, который не должен быть добавлен в ответ.
}}

== Псевдокод ==
<code>
struct interval_tree
interval_tree *left, *right
int x_mid
vector<segment> left_segments, right_segments;

interval_tree build_tree(vector<segment> segments)
if (segment.size() == 0)
return NULL
x_mid = mid_element(segments.all_coordinates)
for (segment s : segments)
if (s.right < x_mid)
left_child.add(s);
if (s.left > x_mid)
right_child.add(s);
if (s.left <= x_mid && s.right >= x_mid)
left_segments.add(s);
right_segments.add(s);
sort(left_segments) // by increasing of x_mid - segment.left
sort(right_segments) // by decreasing of segment.right - x_mid
result.left = build(left_child);
result.right = build(right_child);
result.left_segments = left_segments;
result.right_segments = right_segments;
result.x_mid = x_mid;
return result;

vector<segment> get_ans(interval_tree tree, int q_x)
if (tree == NULL)
return empty_result;
if (q_x < tree.x_mid)
result = get_ans(tree.left, q_x);
if (q_x > tree.x_mid)
result = get_ans(tree.right, q_x);
if (q_x < tree.x_mid)
it = left_segments.size() - 1;
while (it != -1 && left_segment[it].left <= q_x)
result.add(left_segments[it--]);
if (q_x >= tree.x_mid)
it = right_segments.size() - 1;
while (it != -1 && right_segments[it].right >= q_x)
result.add(right_segments[it--]);
return result;
</code>

Викиконспекты - Вклад участника [ru]

Дерево интервалов (interval tree) и пересечение точки с множеством интервалов