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

Пересечение прямоугольника с множеством непересекающихся отрезков (segment tree)

2014-01-16T20:10:06Z

188.162.64.50: /* Построение дерева */

== Задача ==
Есть множество непересекающихся отрезков в <tex>\mathbb{R}^2</tex>, нужно уметь отвечать на запросы, какие из них пересекают границу данного axis-aligned (стороны параллельны осям координат) прямоугольника.

== Дерево отрезков ==
[[Файл:Segment_tree_1.png|400px|thumb|right|Пример дерева отрезков]]
Для решения задачи потребуется структура данных, которая называется дерево отрезков (segment tree). NB: по-русски этими словами принято обозначать несколько [[Дерево_отрезков._Построение | другую]] структуру данных, здесь не о ней.

Пусть <tex>I = \{[x_1 : x_{1}'], [x_2 : x_{2}'], ..., [x_n : x_{n}']\}</tex> — множество отрезков на вещественной оси. Возьмем концы этих отрезков и отсортируем их, получим точки <tex>p_1, p_2, ..., p_m</tex>. Назовем множеством ''элементарных интервалов'' <tex>E = \{ (-\infty : p_1), [p_1 : p_1], (p_1 : p_2), ..., (p_m : +\infty) \}</tex>.

Построим сбалансированное бинарное дерево, листам которого будут соответствовать элементарные интервалы, а внутренним вершинам — объединения интервалов в потомках.
Будем обозначать интервал, соответствующий вершине <tex>v</tex>, <tex>Int(v)</tex>.
В каждой вершине будем хранить соответствующий ей интервал и множество отрезков <tex>I(v)</tex>, таких что <tex>I(v) \subset I</tex> и <tex>\forall [x : x'] \in I(v) : Int(v) \subset [x : x'], Int(parent(v)) \not\subset [x : x']</tex>. По-человечески это значит, что интервал вершины должен полностью лежать внутри отрезка и выше таких вершин нет. По картинке должно быть понятно.

{{Лемма
|about=
Оценка на память
|statement=
Дерево отрезков занимает <tex>O(n \log n)</tex> памяти.
|proof=
Всего элементарных интервалов не больше <tex>4n+1</tex> (в случае, когда все отрезки не пересекаются: для каждого отрезок левее <tex>x</tex>, <tex>[x : x]</tex>, <tex>(x : x')</tex>, <tex>[x' : x']</tex> и еще один <tex>(p_m : +\infty)</tex>). Так как дерево сбалансированное, его глубина <tex>O(\log n)</tex>.

Утверждается, что один отрезок на одной глубине встречается не более двух раз. Пусть это не так, возьмем три упорядоченные вершины <tex>v_1, v_2, v_3</tex>, содержащие этот отрезок. Очевидно, что сосед <tex>v_2</tex> тоже содержит этот отрезок (см. картинку). Тогда этот отрезок должен содержаться в <tex>parent(v_2)</tex>. Противоречие.

[[Файл:Segment_tree_proof.png]]

Глубина <tex>O(\log n)</tex>, всего отрезков <tex>n</tex>, на каждом уровне отрезок встречается <tex>O(1)</tex> раз — победа.
}}

=== Построение дерева ===
Сначала сортируем концы отрезков из <tex>I</tex> за <tex>O(n \log n)</tex>. За <tex>O(n)</tex> собираем сбалансированное дерево (просто поднимаясь от листьев к корню и объединяя интервалы). Осталось найти <tex>I(v)</tex> для вершин дерева. Для этого вставим туда каждый отрезок по такому алгоритму:
def '''InsertSegment'''(v, [x : x']):
if <tex>Int(v) \subset [x : x']</tex>:
v.Add([x : x'])
else:
if <tex>Int(v.Left) \cap [x : x'] \neq \varnothing</tex>:
InsertSegment(v.Left, [x : x'])
if <tex>Int(v.Right) \cap [x : x'] \neq \varnothing</tex>:
InsertSegment(v.Right, [x : x'])
Это работает за <tex>O(\log n)</tex>, потому что на каждом уровне есть не более двух вершин, в которые отрезок нужно вставить и еще не более двух вершин, содержащих его концы. Таким образом, на каждом уровне нужно обработать не более четырех вершин. Итого для всех отрезков получаем <tex>O(n \log n)</tex>.

=== Запрос ===
Теперь научимся отвечать на запрос, какие отрезки содержат заданную точку.
def '''Query'''(v, p, S):
S = S <tex>\cup</tex> I(v)
if !v.IsLeaf:
if <tex>p \in Int(v.Left)</tex>:
Query(v.Left, p)
else
Query(v.Right, p)
Query(root, p, <tex>\varnothing</tex>)
Запрос работает за <tex>O(\log n + k)</tex>, где <tex>k</tex> — размер ответа.

== Алгоритм ==
Чтобы решить исходную задачу, нужно уметь находить, какие отрезки из <tex>I</tex> пересекают axis-aligned отрезок <tex>s</tex>. Рассмотрим случай, когда <tex>s</tex> параллелен оси <tex>y</tex>, для <tex>x</tex> все делается аналогично.

В дереве отрезков будем хранить их проекции на ось <tex>x</tex>. Это позволит найти, какие отрезки пересекают бесконечную вертикальную линию. Осталось найти, какие из них пересекают заданный отрезок.

Используем то, что отрезки не пересекаются, и <tex>[x : x'] \in I(v) \Rightarrow Int(v) \subset [x : x']</tex>: это значит, что отрезки внутри элементарного интервала могут быть вертикально упорядочены. В <tex>I(v)</tex> вместо списка теперь будем хранить дерево поиска.

При запросе будем выдавать только те отрезки, для которых верхняя граница запроса выше точки пересечения с вертикальной линией, а нижняя — ниже (то есть все, что находится между lower_bound и upper_bound в дереве, проверяем выше/ниже поворотом).

Таким образом, обработка одной вершины занимает <tex>O(\log n + k_v)</tex> времени, где <tex>k_v</tex> — количество отрезков в ответе, полученных из вершины <tex>v</tex>, всего посещенных вершин <tex>O(\log n)</tex>, итого <tex>O({\log}^2 n + k)</tex>. Препроцессинг выполняется за <tex>O(n {\log}^2 n)</tex> из-за вставки в дерево поиска.

== Ссылки ==
* [https://en.wikipedia.org/wiki/Segment_tree Английская википедия]
* de Berg, van Kreveld, Overmars, Schwarzkopf "Computational Geometry Algorithms and Applications", p. 231

Пересечение прямоугольника с множеством непересекающихся отрезков (segment tree)

2014-01-16T17:51:02Z

188.162.64.50: /* Дерево отрезков */

== Задача ==
Есть множество непересекающихся отрезков в <tex>\mathbb{R}^2</tex>, нужно уметь отвечать на запросы, какие из них пересекают границу данного axis-aligned (стороны параллельны осям координат) прямоугольника.

== Дерево отрезков ==
[[Файл:Segment_tree_1.png|400px|thumb|right|Пример дерева отрезков]]
Для решения задачи потребуется структура данных, которая называется дерево отрезков (segment tree). NB: по-русски этими словами принято обозначать несколько [[Дерево_отрезков._Построение | другую]] структуру данных, здесь не о ней.

Пусть <tex>I = \{[x_1 : x_{1}'], [x_2 : x_{2}'], ..., [x_n : x_{n}']\}</tex> — множество отрезков на вещественной оси. Возьмем концы этих отрезков и отсортируем их, получим точки <tex>p_1, p_2, ..., p_m</tex>. Назовем множеством ''элементарных интервалов'' <tex>E = \{ (-\infty : p_1), [p_1 : p_1], (p_1 : p_2), ..., (p_m : +\infty) \}</tex>.

Построим сбалансированное бинарное дерево, листам которого будут соответствовать элементарные интервалы, а внутренним вершинам — объединения интервалов в потомках.
Будем обозначать интервал, соответствующий вершине <tex>v</tex>, <tex>Int(v)</tex>.
В каждой вершине будем хранить соответствующий ей интервал и множество отрезков <tex>I(v)</tex>, таких что <tex>I(v) \subset I</tex> и <tex>\forall [x : x'] \in I(v) : Int(v) \subset [x : x'], Int(parent(v)) \not\subset [x : x']</tex>. По-человечески это значит, что интервал вершины должен полностью лежать внутри отрезка и выше таких вершин нет. По картинке должно быть понятно.

{{Лемма
|about=
Оценка на память
|statement=
Дерево отрезков занимает <tex>O(n \log n)</tex> памяти.
|proof=
Всего элементарных интервалов не больше <tex>4n+1</tex> (в случае, когда все отрезки не пересекаются: для каждого отрезок левее <tex>x</tex>, <tex>[x : x]</tex>, <tex>(x : x')</tex>, <tex>[x' : x']</tex> и еще один <tex>(p_m : +\infty)</tex>). Так как дерево сбалансированное, его глубина <tex>O(\log n)</tex>.

Утверждается, что один отрезок на одной глубине встречается не более двух раз. Пусть это не так, возьмем три упорядоченные вершины <tex>v_1, v_2, v_3</tex>, содержащие этот отрезок. Очевидно, что сосед <tex>v_2</tex> тоже содержит этот отрезок (см. картинку). Тогда этот отрезок должен содержаться в <tex>parent(v_2)</tex>. Противоречие.

[[Файл:Segment_tree_proof.png]]

Глубина <tex>O(\log n)</tex>, всего отрезков <tex>n</tex>, на каждом уровне отрезок встречается <tex>O(1)</tex> раз — победа.
}}

=== Построение дерева ===
Сначала сортируем концы отрезков из <tex>I</tex> за <tex>O(n \log n)</tex>. За <tex>O(n)</tex> собираем сбалансированное дерево (просто поднимаясь от листьев к корню и объединяя интервалы). Осталось найти <tex>I(v)</tex> для вершин дерева. Для этого вставим туда каждый отрезок по такому алгоритму:
def '''InsertSegment'''(v, [x : x']):
if <tex>Int(v) \subset [x : x']</tex>:
v.Add([x : x'])
else:
if <tex>Int(v.Left) \cap [x : x ] \neq \varnothing</tex>:
InsertSegment(v.Left, [x : x'])
if <tex>Int(v.Right) \cap [x : x ] \neq \varnothing</tex>:
InsertSegment(v.Right, [x : x'])
Это работает за <tex>O(\log n)</tex>, потому что на каждом уровне есть не более двух вершин, в которые отрезок нужно вставить и еще не более двух вершин, содержащих его концы. Таким образом, на каждом уровне нужно обработать не более четырех вершин. Итого для всех отрезков получаем <tex>O(n \log n)</tex>.

=== Запрос ===
Теперь научимся отвечать на запрос, какие отрезки содержат заданную точку.
def '''Query'''(v, p, S):
S = S <tex>\cup</tex> I(v)
if !v.IsLeaf:
if <tex>p \in Int(v.Left)</tex>:
Query(v.Left, p)
else
Query(v.Right, p)
Query(root, p, <tex>\varnothing</tex>)
Запрос работает за <tex>O(\log n + k)</tex>, где <tex>k</tex> — размер ответа.

== Алгоритм ==
Чтобы решить исходную задачу, нужно уметь находить, какие отрезки из <tex>I</tex> пересекают axis-aligned отрезок <tex>s</tex>. Рассмотрим случай, когда <tex>s</tex> параллелен оси <tex>y</tex>, для <tex>x</tex> все делается аналогично.

В дереве отрезков будем хранить их проекции на ось <tex>x</tex>. Это позволит найти, какие отрезки пересекают бесконечную вертикальную линию. Осталось найти, какие из них пересекают заданный отрезок.

Используем то, что отрезки не пересекаются, и <tex>[x : x'] \in I(v) \Rightarrow Int(v) \subset [x : x']</tex>: это значит, что отрезки внутри элементарного интервала могут быть вертикально упорядочены. В <tex>I(v)</tex> вместо списка теперь будем хранить дерево поиска.

При запросе будем выдавать только те отрезки, для которых верхняя граница запроса выше точки пересечения с вертикальной линией, а нижняя — ниже (то есть все, что находится между lower_bound и upper_bound в дереве, проверяем выше/ниже поворотом).

Таким образом, обработка одной вершины занимает <tex>O(\log n + k_v)</tex> времени, где <tex>k_v</tex> — количество отрезков в ответе, полученных из вершины <tex>v</tex>, всего посещенных вершин <tex>O(\log n)</tex>, итого <tex>O({\log}^2 n + k)</tex>. Препроцессинг выполняется за <tex>O(n {\log}^2 n)</tex> из-за вставки в дерево поиска.

== Ссылки ==
* [https://en.wikipedia.org/wiki/Segment_tree Английская википедия]
* de Berg, van Kreveld, Overmars, Schwarzkopf "Computational Geometry Algorithms and Applications", p. 231