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

Трапецоидная карта — геометрическая структура позволяющая локализоваться на площади за [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{left}p[/math]) — точка, определяющая левую сторону трапецоида или, в случаи треугольника, просто являющаяся левой вершиной.
• правая граница ([math]\operatorname{right}p[/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]

Асимптотика

Запрос

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

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

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

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

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

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

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

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

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

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

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

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

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

а на i-ой итерации уже в трапецоиде [math] \Delta_q(i) [/math] и эти два трапецоида разные.

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

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

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

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

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

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

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

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

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

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

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

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

Память

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

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

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

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

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

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

А тогда Mem = [math]O(n)[/math]

Из этих двух выводов очевидно следует, что время построения карты равно [math]O(nlogn)[/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