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

Задача

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

Дерево отрезков

Пример дерева отрезков

Для решения задачи потребуется структура данных, которая называется дерево отрезков (segment tree). NB: по-русски этими словами принято обозначать несколько другую структуру данных, здесь не о ней.

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

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

Лемма (Оценка на память):

Дерево отрезков занимает [math]O(n \log n)[/math] памяти.

Доказательство:

[math]\triangleright[/math]

Всего элементарных интервалов не больше [math]4n+1[/math] (в случае, когда все отрезки не пересекаются: для каждого отрезок левее [math]x[/math], [math][x : x][/math], [math](x : x')[/math], [math][x' : x'][/math] и еще один [math](p_m : +\infty)[/math]). Так как дерево сбалансированное, его глубина [math]O(\log n)[/math]. Утверждается, что один отрезок на одной глубине встречается не более двух раз. Пусть это не так, возьмем три упорядоченные вершины [math]v_1, v_2, v_3[/math], содержащие этот отрезок. Очевидно, что сосед [math]v_2[/math] тоже содержит этот отрезок (см. картинку). Тогда этот отрезок должен содержаться в [math]parent(v_2)[/math]. Противоречие. Глубина [math]O(\log n)[/math], всего отрезков [math]n[/math], на каждом уровне отрезок встречается [math]O(1)[/math] раз — победа.

[math]\triangleleft[/math]

Построение дерева

Сначала сортируем концы отрезков из [math]I[/math] за [math]O(n \log n)[/math]. За [math]O(n)[/math] собираем сбалансированное дерево (просто поднимаясь от листьев к корню и объединяя интервалы). Осталось найти [math]I(v)[/math] для вершин дерева. Для этого вставим туда каждый отрезок по такому алгоритму:

def InsertSegment(v, [x : x']):
  if [math]Int(v) \subset [x : x'][/math]:
    v.Add([x : x'])
  else:
    if [math]Int(v.Left) \cap [x : x'] \neq \varnothing[/math]:
      InsertSegment(v.Left, [x : x'])
    if [math]Int(v.Right) \cap [x : x'] \neq \varnothing[/math]:
      InsertSegment(v.Right, [x : x'])

Это работает за [math]O(\log n)[/math], потому что на каждом уровне есть не более двух вершин, в которые отрезок нужно вставить и еще не более двух вершин, содержащих его концы. Таким образом, на каждом уровне нужно обработать не более четырех вершин. Итого для всех отрезков получаем [math]O(n \log n)[/math].

Запрос

Теперь научимся отвечать на запрос, какие отрезки содержат заданную точку.

def Query(v, p, S):
  S = S [math]\cup[/math] I(v)
  if !v.IsLeaf:
    if [math]p \in Int(v.Left)[/math]:
      Query(v.Left, p, S)
    else
      Query(v.Right, p, S)
Query(root, p, [math]\varnothing[/math])

Запрос работает за [math]O(\log n + k)[/math], где [math]k[/math] — размер ответа.

Алгоритм

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

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

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

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

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

Ссылки

• Английская википедия
• de Berg, van Kreveld, Overmars, Schwarzkopf "Computational Geometry Algorithms and Applications", p. 231