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

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

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

 Предположим, у нас есть наши координаты, и есть карта мира.
 
 Мы можем найти по карте наше местоположение и сказать в какой области мы находимся.
 Области задаются отрезками. 
 
 Формальная постановка задачи	
 Есть множество отрезков на плоскости.
 Есть запрос (точка q), на выход подается область заданная какими-то отрезками в которой находится q.

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

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

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

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

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

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

Лемма:

Любой face трапецоидной карты ограничен одним или двумя вертикальными отрезками и обязательно двумя не вертикальными отрезками.

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

Именно отсюда берется название стрктуры, так как любой face либо трапеция, либо треугольник.

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

• левая граница(leftp) - точка определяющая левуюы сторону трапецоида или в случаи треугольника просто являющаяся левой вершиной.
• правая граница(rightp) - аналогично левой только справа.

• верхний отрезок(top) и нижний отрезок(bottom) - отрезки ограничивающие трапецоид сверху и снизу.

• трапецоиды называются смежными, если имеют общую вертикальную границу.

• пусть [math]\Delta_1 и \Delta_2[/math] смежны и либо top([math]\Delta_1[/math]) = top([math]\Delta_2[/math]), либо bottom([math]\Delta_1[/math]) = bottom([math]\Delta_2[/math])

Тогда [math]\Delta_1[/math],[math]\Delta_2[/math] называют либо большими левыми соседями, либо меньшими.

Теорема:

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

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

[math]\triangleright[/math]

вершины Откуда берутся вершины. 4 вершины уходит на оболочку R. 2*n концы отрезков 2*2n пересечения вертикальных лучей из концов отрезков с другими отрезками или оболочкой трапецоиды Будем смотреть на левую сторону трапецоида.

[math]\triangleleft[/math]

Хранить трапецоиды можно в чем угодно. Вместе с самим трапецоидом, стоит хранить leftp, rightp, top и bottom так же следует хранить соседей трапецоида.

---

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

Поисковая структура(в дальнейшем [math] D[/math]) предсталяет из себя ацикличный граф с одним корнем и каждому трапецоиду в структре соответствует один лист.

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

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

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

Второй тип узла - отрезок.

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

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

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

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

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

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

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

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

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

Алгоритм

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

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

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

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

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

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

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

Алгоритм

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

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

• Удалили их.

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

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

---

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

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

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

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

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

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

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

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

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

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

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

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

Асимптотика

Запрос

Запрос производится за время пропорцианальное глубине графа(поисковой структуры). Если считать, что на каждой итерации глубина увеливается максимум на 3, то время работы в худшем случаи будет O(3n). Но мы вспоминаем, что порядок добавления отрезков рандомный, а потому наврядли всегда будет худший случай.

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

Эта величина зависит только от порядка добаления отрезков(если множество установлено).

Будет искать математическое ожидание глубины графа.

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

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

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

Наша задача, понять чем ограничена P_i.

Пусть [math] \Delta_q(i) [/math] - трапецоид содержащий q на i-ой итерации.

Скажем, что произошло изменение на i-ой итерации если [math] \Delta_q(i) [/math] != [math] \Delta_q(i - 1) [/math]

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

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

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

Либо этот отрезок был top или bottom, либо его концы были leftp или rightp.

Представим, что наш трапецоид [math] \Delta_q(i) [/math] исчез когда мы удалили текущий отрезок. Он мог исчезнуть только если исчез один из указателей(top, bottom ...).

Рассмотрим вероятность этого исчезновения.

Так как отрезки мы добавляли в рандомном порядке, вероятность текущему отрезку быть top или bottom равна 1/i.

leftp исчезает только в том случаи если leftp была концом теккущего отрезка. А потому эта вероятность тоже равна 1/i. Аналогично для rightp.

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

[math]\sum^{n}_{i=1}E[X_i][/math] <= [math]\sum^{n}_{i=1}3P_i \lt = \sum^{n}_{i=1}12/i \lt =12\sum^{n}_{i=1}(1/i) \approx 12*log(n)[/math]

Ура

Память

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

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

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

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

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

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

А тогда Mem = O(n)

Из этих двух выводов очевидно следует, что время построения карты равно O(nlogn)

Реализация

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

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

struct Trapezoid

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

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

TrapezoidMap(S - segments)

 Строим оболочку(просто находим крайние точки множества отрезков по четырем направлениям)
 Строим рандомную перестановку отрезков
 for i[math]\leftarrow[/math] 1 to n
 do ищем множество трапецоидов пересекаемых отрезком [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