Трапецоидная карта

Трапецоидная карта — геометрическая структура позволяющая локализоваться на площади за [math]\mathcal{O}(\log(n))[/math].

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

Предположим, у нас есть наши координаты, и есть карта мира.

Мы можем найти по карте наше местоположение и сказать в какой стране мы находимся. Области задаются замкнутыми ломаными.

Формальная постановка задачи

Есть множество отрезков на плоскости. Есть запрос (точка [math]q[/math]), на выходе — область, в которой находится точка [math]q[/math].

Структура данных

трапецоидная карта

• Геометрическая

У нас есть множество отрезков, ограниченных оболочкой [math]R[/math](это не выпуклая оболочка, а просто мнимая граница плоскости, за которую не вылезают отрезки).

Мы договариваемся, что никакие две точки не лежат на одной вертикали(в противном случае всё ещё противнее).

Трапецоидная карта множества отрезков [math]S[/math] — это эти отрезки и из каждой точки выпущены два луча — вверх и вниз, до первого пересечения с другим отрезком или с оболочкой [math]R[/math].

Лемма:

Любой [math]\operatorname{face}[/math] трапецоидной карты ограничен одним или двумя вертикальными отрезками и обязательно двумя не вертикальными отрезками.

навигация в трапецоидной карте

Именно отсюда берется название структуры, так как любой [math]\operatorname{face}[/math] либо трапеция, либо треугольник.

Введем обозначения для навигации по карте.

• левая граница ([math]\operatorname{leftp}[/math]) — точка, определяющая левую сторону трапецоида или, в случаи треугольника, просто являющаяся левой вершиной.
• правая граница ([math]\operatorname{rightp}[/math]) — аналогично левой, только справа.
• верхний отрезок ([math]\operatorname{top}[/math]) и нижний отрезок([math]\operatorname{bottom}[/math]) — отрезки, ограничивающие, трапецоид сверху и снизу.
• трапецоиды называются смежными, если имеют общую вертикальную границу.
• пусть [math]\Delta_1[/math] и [math]\Delta_2[/math] смежны и либо [math]\operatorname{top}(\Delta_1) = \operatorname{top}(\Delta_2)[/math], либо [math]\operatorname{bottom}(\Delta_1) = \operatorname{bottom}(\Delta_2)[/math]. Тогда [math]\Delta_1[/math] и [math]\Delta_2[/math] называют либо нижними, либо верхними левыми соседями.

Теорема:

Трапецоидная карта, построенная на [math]n[/math] отрезках содержит максимум [math]6n+4[/math] вершины и максимум [math]3n+1[/math] трапецоид.

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

[math]\triangleright[/math]

вершины, а точнее откуда они берутся. варианты leftp([math]\Delta[/math]) 4 вершины уходит на оболочку [math]R[/math] [math]2 \cdot n[/math] концы отрезков [math]2 \cdot 2n[/math] пересечения вертикальных лучей из концов отрезков с другими отрезками или оболочкой трапецоиды Будем смотреть на левую сторону трапецоида. У каждого трапецоида есть точка [math]\operatorname{leftp}(\Delta)[/math]. Либо это конец какого-то отрезка, либо это левый нижний угол оболочки. При этом можно сразу сказать, что левый и нижний угол будут соответствовать только одному трапецоиду. Далее заметим, что правый конец отрезка может быть [math]\operatorname{leftp}(\Delta)[/math] только для одного трапецоида. Левый конец может быть [math]\operatorname{leftp}(\Delta)[/math] максимум для двух трапецоидов. Из этого следует, что количество трапецоидов [math]n + 2n + 1 = 3n + 1[/math].

[math]\triangleleft[/math]

Хранить трапецоиды можно в чем угодно. Вместе с самим трапецоидом, стоит хранить [math]\operatorname{leftp}[/math], [math]\operatorname{rightp}[/math], [math]\operatorname{top}[/math] и [math]\operatorname{bottom}[/math]. Так же следует хранить соседей трапецоида.

---

• Поисковая структура

Поисковая структура представляет из себя ациклический граф с одним корнем и соответствующими трапецоидам листьями.

У каждого узла есть два ребенка. При этом узел может быть двух типов.

навигация в трапецоидной карте

• Первый тип узла - точка, соответствующая концу отрезка.
• Второй тип узла - отрезок.

Во время запроса мы двигаемся по графу от его корня до момента, когда окажемся в листе. Это и будет означать, что точка находится внутри трапецоида.

Если мы находимся не в листе, то мы должны опредетиться, в каком из детей мы окажемся дальше.

Еcть два правила:

• Если текущий узел соответсвует вершине, то смотрим левее или правее мы находимся(проверка по [math]x[/math]-координате).
• Если текущий узел соответствует отрезку, то смотрим выше или ниже мы находимся(проверка по [math]y[/math]-координате).

• Плохие случаи:

Мы находимся на одной вертикали с вершиной

Мы находимся на отрезке

(Решение: молиться, или просто обрабатывать вручную.)

Алгоритм

простой случай

Во время построения трапецоидной карты(в дальнейшем [math]T[/math]) алгоритм так же строит структуру для поиска.

Так как трапецоидная карта — геометрическая структура, а основные операции ведутся именно с поисковой, основной упор делается на неё.

Наш алгоритм добавляет отрезки по одному и, после каждого добавления, модидицирует [math]T[/math] и [math]D[/math].

Порядок добавления отрезков

От порядка добавления зависит время запроса. Как? Время запрос пропорцианально глубине графа.

Считается, что если добавлять отрезки в случайном порядке, то время будет хорошим. Почему и какое время будет достигаться, расписано дальше.

Алгоритм

• Добавили отрезок.

• Нашли все трапецоиды, которые пересек новый отрезок.

• Удалили их.

• Создали новые трапецоиды.

сложный случай

Поиск трапецоидов, которые пересек отрезок

Чтобы модифицировать карту, мы должны понять, где произошло изменение.

Оно произошло в тех трапецоидах, которые пересек текущий отрезок, или можно сказать, что трапецоид с [math]i-1[/math]-ой итерации не будет в [math]i[/math]-ой только если его пересек отрезок.

Пусть якобы есть множество трапецоидов [math]\Delta_0, \Delta_1, \Delta_2 \ldots \Delta_k[/math], упорядоченное по [math]s_i[/math]

Пусть [math]\Delta_{j+1}[/math] — один из правых соседей [math]\Delta_j[/math]. Так же, при этом не сложно понять, каким соседом он является.

Если [math]\operatorname{rightp} \Delta_j[/math] лежит выше [math]s_i[/math], то сосед нижний и наоборот.

Это значит, что, если мы знаем первый трапецоид, то мы можем найти остальные просто обходя по карте соседей справа.

Чтобы найти первый трапецоид, нужно просто локализовать правый конец в текущей карте.

update

Рассмотрим подробнее последние две части

Есть два случая.

• Простой — отрезок не пересекает ни одного трапецоида, то есть целиком внутри.

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

Важно не забыть правильно определить соседей новых трапецоидов.

В случае, если какие-то трапецоиды выродятся в треугольники, будет не четыре новых трапецоида, а 2 или 3. Слава богу это не самая большая проблема.

• Сложный — отрезок пересекает сразу несколько трапецоидов.

Итак наш отрезок пересекает трапецоиды [math]\Delta_0, \Delta_1, \Delta_2 ... \Delta_k[/math].

Сначала добавляем вертикальные лучи из концов текущего отрезка. Это нужно, чтобы модифицировать [math]\Delta_0[/math] и [math]\Delta_k[/math]. Теперь мы должны удалить соответствующие листья и на их место поставить те новые, которые появились из-за изменения лучей.

Дальше мы модифицуруем вертикальные лучи, которые пересекают текущий отрезок. Этот процесс происходит достаточно быстро, так мы храним много информацию об этих лучах.

[math]\Delta_0, \Delta_1, \Delta_2 \ldots \Delta_k[/math].

Случай коллизии

Рассмотрим момент, когда мы мы строим карты. Мы должны добавить очередной отрезок.

Предположим, левый конец отрезка лежит на одной вертикале с уже добавленной в карту точкой [math] p [/math].

Скажем, что наша точка лежит правее, чем та, которая уже есть. В случае, если мы попали на уже созданный отрезок, мы скажем, что находимся, например, ниже его.

Что при этом произойдет.

• С геометрической точки зрения, появится ещё несколько трапецоидов, как в случае, если бы вновь добавленная точка была правее на [math] \varepsilon \rightarrow 0[/math].

А значит, у трапецоида по прежнему не более двух правых соседей.

• С точки зрения поисковой структуры мы по-прежнему можем локализоваться. По крайней мере, узел, соответствующий точке [math] p [/math] будет иметь правым сыном нашу точку.

Итого, слова "трапецоидные карты просты отсутствие случаев" появляются именно отсюда, так как, казалось бы, неприятный случай будет прописан заменой [math]\textless [/math] на [math] \le [/math]

Асимптотика

Запрос

Предположим у нас есть запрос на локализацию точки [math]q[/math]. Время, затраченное, на этот запрос будет линейно зависеть от глубина графа.

При добавлении в карту очередного отрезка(в дальнейшем, итерация алгоритма), глубина графа увеличивается максимум на 3. Из этого мы можем сделать простую оценку.

Наибольшее время на запрос, которое мы можем потратить — [math]3n[/math]. Произойдет это в самом ужасном из самых ужасных случаев.

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

Рассмотрим путь, пройденный точкой по графу. Каждый узел был создан на какой-то итерации цикла. Обозначим за [math]X_i[/math] количество узлов, созданных на итерации [math]i[/math].

Так как никто не выбирал исходное множество отрезков и запрос [math]q[/math], [math]X_i[/math] — рандомная величина, зависящая только от рандомного порядка добавления отрезков.

[math]E[\sum^{n}_{i=1}X_i] = \sum^{n}_{i=1}E[X_i][/math]

Как уже упоминалось, на каждой итерации добавляется не более 3 узлов, а значит [math]X_i \leq 3[/math].

Считая, что [math]P_i[/math] — вероятность того, что существует узел, который встречается при нашем запросе, созданный на [math]i[/math]-ой итерации.

[math]\sum^{n}_{i=1}E[X_i] \lt = \sum^{n}_{i=1}3P_i[/math]

Начинаем оценивать [math] P_i [/math].

Что значит, что узел был создан на [math]i[/math]-ой итерации и встретился при запросе [math]q[/math]?

Это значит, что на [math]i-1[/math]-ой итерации мы локализовывали [math]q[/math] в трапецоиде [math]\Delta_q(i-1)[/math],а на [math]i[/math]-ой итерации уже в трапецоиде [math] \Delta_q(i) [/math] и эти два трапецоида разные.

То есть, после добавления непонятно чего в карту, трапецоид изменился.

Таким образом [math]P_i = P(\Delta_q(i) \ne \Delta_q(i - 1))[/math].

Если эти два трапеецоида не равны, значит на i-ой итерации трапецоид [math]\Delta_q(i)[/math] был одним из созданных при модификации.

Заметим, что все трапецоиды, созданные на этой итерации, были смежны текущему отрезку([math]s_i[/math]).

Значит либо [math]s_i = \operatorname{top} \Delta_i[/math] или [math]\operatorname{bottom} \Delta_i[/math], либо концы [math]s_i = \operatorname{leftp} \Delta_i[/math] или [math]\operatorname{rightp} \Delta_i[/math].

Зафиксируем множество отрезков на [math]i[/math]-ой итерации. Тогда состояние трапецоидов никак не будет зависеть от порядка добавленных отрезков.

Тогда, вероятность изменения трапецоида — это его вероятность исчезнуть, если удалится [math]s_i[/math].

Тогда переходим, к [math]\operatorname{top} \Delta_i[/math] и т.п. так как мы уже говорили, что [math]s_i[/math] будет определенной стороной при навигации.

Отрезки добавлялись рандомно, поэтому, в качестве [math]s_i[/math] мог быть любой отрезок из [math]S_i[/math]. А, тогда, вероятность для всех сторон [math]\frac1i[/math].

Суммируем по всем 4 сторонам.

Таким образом [math]P_i = P( \Delta_q(i) \ne \Delta_q(i - 1)) = P( \Delta_q(i) \in \Delta_q(i - 1) ) \le \frac4i[/math]

[math]\sum^{n}_{i=1}E[X_i] \le \sum^{n}_{i=1}3P_i \le \sum^{n}_{i=1}\frac{12}i \le 12\sum^{n}_{i=1}(1/i) \approx 12 \cdot log(n)[/math]

Память

Заметим, что количество трапецоидов, как мы доказали раньше, равно [math]\mathcal{O}(n)[/math], поэтому мы должны оценить количество узлов созданых на [math]i[/math]-ой итерации.

А результирующее выражение для памяти тогда будет

[math]\mathrm{Mem} = \mathcal{O}(n) + \sum^{n}_{i=1}[/math] количество узлов созданное на [math]i[/math]-ой итерации

Обозначив за [math]k_i[/math] количество узлов, созданное на [math]i[/math]-ой итерации

[math]\mathrm{Mem} = \mathcal{O}(n) + \sum^{n}_{i=1} E[k_i][/math]

Используя вывод из предыдущей части получаем, что [math]E[k_i] \le \frac{\mathcal{O}(i)}i = \mathcal{O}(1)[/math]

А тогда [math]\mathrm{Mem} = \mathcal{O}(n)[/math]

Из этих двух выводов очевидно следует, что время построения карты равно [math]\mathcal{O}(n \log n)[/math].

Реализация

Здесь будут рассмотрены некоторые основные моменты реализации Это только идеи, в коде все выглядит примерно в 50 раз хуже.(по количеству строк)

Класс "трапецоид"

struct Trapezoid
  Trapezoid next
  Trapezoid up
  Trapezoid down
  Trapezoid end
  Segment top
  Segment bottom
  Point left
  Point right

Построение трапецоидной карты

TrapezoidMap(S - segments)
  Строим оболочку(просто находим крайние точки множества отрезков по четырем направлениям)
  Строим рандомную перестановку отрезков
  for для всех
    ищем множество трапецоидов пересекаемых отрезком [math]s_i[/math]. //это специальная функция//
    Удаляем это множество из карты и добавляем новые узлы появившиеся из-за [math]s_i[/math] в поисковой структуре
    Аналогично для просто карты

Поиск трапецоидов, которых пересекает отрезок

LookforTrapezoid([math]s_i[/math] - segment)
  Запоминаем левый и правый конец [math]s_i[/math]  
  Делаем запрос на левый конец в карте.
  j [math]\leftarrow[/math] 0;
  while q [math]\in[/math] правый от rightp(трапецоид_j)
    do if rightp(трапецоид_j) над [math]s_i[/math]
      then ставим трапецоид_(j+1) нижним правым соседом трапецоид_j.
      else ставим трапецоид_(j+1) верхним правым соседом трапецоид_j.
    j [math]\leftarrow[/math] j+1

Ссылки

Lecture notes from stanford, Seidel