Изменения

==Решение методом полос= Монотонный метод ===[[Файл:cgslabs.png|200px|right]]Проведём через каждую вершину вертикальную прямую. Получим полосы (slabs). Пусть каждой полосе соответствует точка, через которую проведён левый край полосы. Будем хранить отсортированный массив <tex>x</tex>-координат, тогда за <tex>O(\log n)</tex> можно найти, в какой полосе лежит <tex>P</tex>.

В каждой полосе отрезки{{Определение|id=def_monotone_polygon|definition=Простой многоугольник <tex>P</tex> называется '''монотонным''' относительно прямой <tex>l</tex>, составляющие ППЛГесли любая <tex>l'</tex>, могут пересекаться только в концахтакая что <tex>l' \perp l</tex>, причём эти точки пересекает стороны <tex>P</tex> не более двух раз (результатом пересечения могут лежать <tex>l'</tex> и <tex>P</tex> может быть только на прямых, ограничивающих полосы (по построениюодин отрезок или точка). Получается, что внутри каждой полосы можно отсортировать отрезки, которые лежат в ней, например, снизу вверх. Тогда, найдя нужную полосу, можно быстро найти нужный отрезок.}}

===Персистентные деревья=={{Определение|definition=Персистентные структуры данных — это структурыМногоугольник, боже царя хранящие историю своих изменений. Персистентность бывает полная (когда можем изменять любую версию) и частичная (когда можем изменить только последнюю версию, но запросы можем делать на всех)монотонный относительно <tex>y</tex>-оси называется '''<tex>y</tex>-монотонным'''.}}

Можно усовершенствовать этот способ. Теперь Суть данного метода заключается в каждой ноде будет храниться номер версии и поля для ленивого изменения дерева: фиксированное количество запасных указателей left и right и номера версий для них. Когда мы хотим изменить нодутом, вместо копирования записываем изменения в запасные указателичтобы разбить многоугольник на монотонные части, если они ещё есть, иначе создаём новую ноду и соответственно исправляем её предкаа затем триангулировать каждую из них. Для поиска по версиям используем бинпоиск. Этот способ называется limited node copying, для него нужно O(n) памяти, потому что амортизированно за один апдейт копируем O(1) нод=== Разбиение многоугольника на монотонные части ====[[Файл:Split-merge.png|500px|thumb||Пять типов вершин]]

Рассмотрим самую верхнюю — максимальную по координате <tex>y</tex> вершину. Будем идти вниз по рёбрам до самой нижней — соотвественно минимальной по <tex>y</tex> вершине, то есть таким образом, что для некоторой вершины <tex>j</tex>: <tex>y_j > y_{j+1}</tex>. '''Поворотной''' назовём вершину <tex>i</tex>, на которой направление обхода будет меняется: <tex>y_{i-1} > y_i</tex> и <tex>y_i < y_{i+1}</tex>. Опишем более подробно этот тип вершин. Уточним понятния ''выше'' и ''ниже'': точка <tex>p</tex> лежит ''ниже'' точки <tex>q</tex>, если <tex>p_y < q_y</tex> или если <tex>p_y =q_y</tex> и <tex>p_x > q_x</tex>, соответственно точка <tex>p</tex> лежит ''выше'' точки <tex>q</tex>, если <tex>p_y > q_y</tex> или если <tex>p_y ==Локализация в полосе===Воспользуемся сбалансированным частично персистентным деревом q_y</tex> и <tex>p_x < q_x</tex>. Это было сделано для хранения отрезков в полосах. Каждая полоса — это новая версия дереватого, чтобы избежать неопределённых ситуаций с вершинами, у которых <tex>y</tex>-координаты равны.

==Время Обозначим за <tex>\phi</tex> внутренний угол при некоторой вершине и память==определим далее пять типов вершин, четыре из которых являются поворотными:* '''''start вершина''''' — два её соседа лежат ниже её самой и <tex> \phi < \pi </tex>На запрос нужно * '''''split вершина''''' — два её соседа лежат ниже её самой и <tex>O(\log n)phi > \pi </tex>, на препроцессинг * '''''end вершина''''' — два её соседа лежат выше её самой и <tex>O(n \log n)phi < \pi </tex>; памяти нужно * '''''merge вершина''''' — два её соседа лежат выше её самой и <tex>O(n)\phi > \pi </tex>* '''''regular вершина''''' — не является поворотной, в отличие от остальных, другими словами один её сосед находится выше, а другой ниже её самой.

{{Лемма|statement==Алгоритм Киркпатрика=Многоугольник <tex>P</tex> является <tex>y</tex>-монотонным, если в нём отсутствуют split и merge вершины.|proof=Существует ли метод локализации со временем поиска за Предположим, что <tex>P</tex> не <tex>O(\log n)y</tex>-монотонный. Тогда докажем, использующий менее чем квадратичную память? Эта задача оставалась что <tex>P</tex> содержит split и merge вершины. Поскольку <tex>P</tex> не решенной довольно долго<tex>y</tex>-монотонный, существует горизонтальная прямая <tex>l</tex>, которая пересекает его стороны более двух раз. Но все же была решена Липтоном Выберем <tex>l</tex> таким образом, чтобы самой левой компонентой пересечения <tex>l</tex> и Тарьяном <tex>P</tex> был бы отрезок <tex>pq</tex>. Далее будем двигаться наверх по сторонам <tex>P</tex>, начиная от точки <tex>q</tex>. В результате в 1977-1980 ггнекоторой точке <tex>r</tex>, где <tex>r \neq p</tex> (случай '''(a)''' на рисунке), прямая <tex>l</tex> снова пересечёт одну из сторон <tex>P</tex>. Отсюда самая высокая точка, которую мы достигли во время движения по сторонам <tex>P</tex>, будет split вершиной. [[Файл:Proof_lemma. Но их метод оказался jpg|450px]] Если же <tex>r = p</tex> (случай '''(b)''' на столько громоздкимрисунке), а оценки времени его эффективности содержат слишком большую константуначём опять двигаться по сторонам <tex>P</tex> теперь уже вниз. Как и в предыдущем случае найдётся некоторая точка <tex>r'</tex>, что сами авторы не считали этот метод практичнымкоторая будет результатом пересечения <tex>l</tex> и <tex>P</tex>. При этом <tex>r' \neq p</tex>, но его существование заставляет думатьв противном случае <tex>l</tex> будет пересекать <tex>P</tex> только два раза, что может найтись практичный алгоритм с временной оценкой противоречит выбору <tex>O(\log n)l</tex> и линейной памятью.Аналогично предыдущему случаю, выберем теперь самую низкую точку, которую мы достигли во время движения по сторонам P. Она будет merge вершиной.}}

Недавно Киркпатриком был предложен оптимальный метод, дающий ответ на ожидания Липтона и Тарьяна, {{---}} детализация триангуляции.===ПредобработкаАлгоритм ===<wikitex>[[Файл:кирк1.png|right|200px]]Пусть планарный N-вершинный граф задает триангуляцию нашего многоугольника (если это не такЧтобы сделать многоугольник монотонным, то воспользуемся методом триангуляции многоугольника за время $O (n \log n)$. Напомним, что триангуляция на множестве нужно избавиться от split и merge вершин путём проведения непересекающихся дигоналей из таких вершин $V$ есть планарный граф с не более чем $3 |V| - 6$ ребрами ([[Формула_Эйлера |формула Эйлера]]). Для удобства описания алгоритма поместим нашу триангуляцию в охватывающий треугольник и построим триангуляцию области между нашими объектами. После этого преобразования все триангуляции будут обладать тремя границами и ровно $3 |V| - 6$ ребрами.</wikitex>

===Структура данных===Рассмотрим горизонтальную заметающую прямую <tex>l</tex>, будем перемещать её сверху вниз вдоль плоскости на которой лежит исходный многоугольник <tex>P</tex>. Будем останавливать её в каждой вершине многоугольника. В тот момент, когда на пути заметающей прямой встречается split или merge вершина её нужно соединить с вершиной, у которой расстояние до <tex>l</tex> минимально, при этом она должна лежать соответственно выше или ниже <tex>l<wikitex/tex>.[[Файл:кирк2Split_case.pngjpg|right200px|200px]][[Файл:кирк3.pngthumb|right|300pxОбработка ''split'' вершины <tex>v_i</tex>]]Итак, имеется N-вершинная триангуляция $G$, и пусть строится последовательность триангуляций $S_1, S_2, \dots, S_{h(N)}$, где $S_1 = G$, а $S_i$ получается из $S_{i - 1}$ по следующим правиламРассмотрим каждый случай подробнее:* Шаг 1. Удалим некоторое количество неграничных и независимых (попарно несмежных друг с другом) вершин и инцидентные им ребра (от выбора этого множества напрямую зависит оптимальность алгоритма).* Шаг 2. Построить триангуляцию получившихся в результате шага 1 многоугольников.Таким образом $S_{h(N)}$ состоит из одного треугольника. Заметим, что все триангуляции имеют одну общую границу, так как удаляются только внутренние узлы. Далее, будем обозначать все треугольники как $R$, а также будем говорить, что треугольник $R_ij$ принадлежит триангуляции $S_i$, если он был создан на шаге (2) при построении этой триангуляции.

Теперь построим структуру данных $T$ # '''''Split вершина'''''. Пусть <tex>e_j</tex> и <tex>e_k</tex> — ближайшее левое и правое ребро относительно split вершины <tex>v_i</tex>, которые <tex>l</tex> пересекает в данный момент. Нам нужно найти вершину, лежащую между <tex>e_j</tex> и <tex>e_k</tex>, наиболее приближённую к <tex>l</tex>, либо если такой точки не существет выбрать минимальную из верхних вершин <tex>e_j</tex> и <tex>e_k</tex>. Для этого будем хранить указатель на искомую вершину у левого ребра <tex>e_j</tex>, который можно заранее вычислить. Тип вершины, хранящийся в <tex>helper</tex> не имеет значения. Таким образом, чтобы построить диагональ для поискаsplit вершины нужно обратиться к указателю <tex>helper(e_j)</tex> её левого ребра, которое <tex>l</tex> пересекает в данный момент.# '''''Merge вершина'''''. Эта структура представляет собой направленный ацикличный графВ отличие от случая со split вершиной заранее вычислить указатель <tex>helper</tex> нельзя, поскольку merge вершина <tex>v_i</tex> должна быть соединена с вершиной, вершинами которого будут наши треугольникилежащей ниже заметающей прямой <tex>l</tex>. Определим эту структуру следующим образом: из треугольника $R_k$ будет вести ребро Для этого в треугольник $R_j$<tex>helper(e_j)</tex> - левого относительно <tex>v_i</tex> ребра запишем саму <tex>v_i</tex>. Далее спускаем заметающую прямую вниз к следующей вершине <tex>v_m</tex>, обращаемся к <tex>helper</tex>'у её левого ребра. Проверяем, если при построении $S_i$ из $S_там хранится merge вершина, строим диагональ <tex>v_{i-1}$ мы имеем* $R_j$ удалятся из $S_v_{i - 1m}$ на шаге (</tex>. Последняя проверка осуществляется для любого типа вершины, кроме split, согласно п.1).* $R_k$ создается [[Файл:Merge_case_1_2.jpg|500px|thumb|center|Обработка ''merge'' вершины <tex>v_i</tex>. На рисунке слева <tex>v_i</tex> записывается в $S_качестве <tex>helper</tex>'а своего левого ребра. На правом рисунке ближайшая вершина <tex>v_m</tex> при обращении к своему левому ребру <tex>helper(e_j)</tex> находит <tex>v_i</tex> и образует диагональ <tex>v_{i}$ на шаге (2)* $R_j \cap R_k \ne \varnothing $v_m</tex>]]

Очевидно=== Структуры данных ===В подходе, описанном выше, требуется находить пересечения заметающей прямой и левых ребёр многоугольника. Создадим двоичное дерево поиска <tex>T</tex>, в листьях которого будем хранить рёбра, пересекающие <tex>l</tex>, такие, что треугольники внутренняя область многоугольника будет лежать справа от них самих. С каждым таким ребром будем хранить его <tex>helper</tex>. Порядок следования листьев в дереве соответствует порядку следования рёбер в многоугольнике: слева направо. Дерево изменяется в зависимости от текущего состояния заметающей прямой. Создадим приоритетную очередь <tex>Q</tex> из $S_1$ (и только они) не вершин, в которой приоритетом будет <tex>y</tex>-координата вершины. Если две вершины имеют исходящих реберодинаковые <tex>y</tex>-координаты, больший приоритет у левой. Вершины будут добавляться на "остановках" заметающей прямой.

Для ясности Многоугольник <tex>P</tex> и добавленные в процессе диагонали удобно изобразить $T$ хранить в рассмотренном виде, то есть помещая его узлы в горизонтальные строки, каждая из которых соответствует какой-нибудь триангуляции. Последовательность триангуляций и соответствующая ей структура $T$ показаны на рисунке. Треугольники пронумерованы в порядке их появления. Кружком обведены вершины, которые удалены на данном шаге. списка </wikitextex>====Выбор множества удаляемых вершин====D<wikitex/tex>Как уже упоминалось, от выбора множества вершит триангуляции, которые будут удалены при построении $S_i$ по $S_{i-1}$ существенно зависит эффективность метода. Предположим, что можно выбрать это множество так, чтобы выполнялись следующие рёбер с двойными связями (''свойстваDCEL — doubly-connected edge list'' ($N_i$ обозначает число вершин в $S_i$):, так как потом это обеспечит эффективный доступ к каждой из частей, которые нужно будет триангулировать.

=== Псевдокод === MakeMonotone(P) Construct(D); Construct(Q); // функция Construct создаёт объекты <tex>D</tex> и <tex>Q</tex> , описанные выше. bst T = new bst(); while Q <tex> \neq \varnothing </tex> Remove <tex>v_{max}</tex> from Q // удаление вершины с наивысшим приоритетом из <tex>Q</tex> switch (Type_of_vertex(<tex>v_{max}</tex>)): // определение типа вершины case 'start': HandleStartVertex(<tex>v_{max}</tex>); case 'Свойство 1end': HandleEndVertex(<tex>v_{max}</tex>); case 'split': HandleSplitVertex(<tex>v_{max}</tex>); case 'merge'. $N_i = a_i N_: HandleMergeVertex(<tex>v_{i-1max}$, где $a_i \le a < 1$ для $i = 2,\dots , h/tex>); case 'regular': HandleRegularVertex(N<tex>v_{max}</tex>)$.;

'''Свойство 2'''. Каждый треугольник $R_i \in S_i$ пересекается не более чем с $H$ треугольниками из $S_{i[[Файл:Split-merge -1}$ и наоборотresult.Первое свойство немедленно влечет за собой следствие, что $h(N) \le \left \lceil \log_{1/a}N \png|470px|thumb|right \rceil = O(log N)$, поскольку при переходе от $S_{i-1}$ к $S_i$ удаляется по меньшей мере фиксированная доля вершин.]]

Также Опишем теперь каждый метод из этих свойств следует, что память для $T$ равна $O(N)$. Действительно, заметим, что эта память используется для хранения узлов и указателей на их потомков. Из [[Формула_Эйлера|теоремы Эйлера]] о плоских графах следует, что $S_i$ содержит $F_i < 2N_i$ треугольников. Число узлов в $T$, представляющих треугольники из $S_i$, не превосходит $F_i$ (только те треугольники, которые действительно принадлежат $S_i$, появляются на соответствующем «ярусе» $T$). Отсюда следует, что общее число узлов в $T$ меньше, чем$2(N_1 + N_2 + \dots + N_{h(N)}) \le 2N_1(1 + a + a^2 + \dots + a^{h(N) - 1}) < \frac{2N}{1 - a}$.Что касается памяти, используемой под указатели, то по свойству 2 каждый узел имеет не более $H$ указателей, поэтому не более $\frac{2NH}{1-a}$ указателей появится в $T$. Это доказывает последнее утверждение.последнего switch:

Покажем теперь HandleStartVertex(<tex>v_{i}</tex>) Insert <tex>e_{i}</tex> in T <tex>helper(e_{i}) \leftarrow v_i</tex>  HandleSplitVertex(<tex>v_{i}</tex>) edge <tex>e_j</tex> = <tex>l \cap P</tex> Search <tex>e_j</tex> in T Insert edge(<tex>v_{i}</tex>, что критерий выбора множества удаляемых <tex>helper(e_{j})</tex>) in D <tex>helper(e_{j}) \leftarrow v_i</tex> Insert <tex>e_{i}</tex> in T <tex>helper(e_{i}) \leftarrow v_i</tex> В последующих трех функциях обработки вершины <tex>v_i</tex> происходит обращение к смежному ребру <tex>e_{i-1}</tex>. Это сделано для вершин, удовлетворяющий вышеописанным свойствамотносительно которых внутренняя область <tex>P</tex> лежит справа от них самих (вершина <tex>v_6</tex>), либо для двух подряд идущих merge вершин, существуеттаких как <tex>v_2</tex> и <tex>v_8</tex>.  HandleEndVertex(<tex>v_{i}</tex>) if (Type_of_vertex(<tex>helper(e_{i-1})</tex> = 'merge') Insert edge(<tex>v_{i}</tex>, <tex>helper(e_{i-1})</tex>) in D Delete <tex>e_{i-1}</tex> from T  HandleMergeVertex(<tex>v_{i}</tex>) if (Type_of_vertex(<tex>helper(e_{Теоремаi-1})</tex> = 'merge')|about Insert edge(<tex>v_{i}</tex>, <tex>helper(e_{i-1})</tex>) in D Delete <tex>e_{i-1}</tex> from T edge <tex>e_j</tex> = <tex>l \cap P</tex> Search <tex>e_j</tex> in T if (Type_of_vertex(<tex>helper(e_{j})</tex> ='merge')критерий выбора множества удаляемых вершин Insert edge(<tex>v_{i}</tex>, <tex>helper(e_{j})</tex>) in D <tex>helper(e_{j}) \leftarrow v_i</tex>  HandleRegularVertex(<tex>v_{i}</tex>) if (interior of <tex>P</tex> lies to the right of <tex>v_{i}</tex>) then if (Type_of_vertex(<tex>helper(e_{i-1})</tex> = 'merge') Insert edge(<tex>v_{i}</tex>, <tex>helper(e_{i-1})</tex>) in D Delete <tex>e_{i-1}</tex> from T Insert <tex>e_{i}</tex> in T <tex>helper(e_{i}) \leftarrow v_i</tex> else edge <tex>e_j</tex> = <tex>l \cap P</tex> Search <tex>e_j</tex> in T if (Type_of_vertex(<tex>helper(e_{j})</tex> = 'merge') Insert edge(<tex>v_{i}</tex>, <tex>helper(e_{j})</tex>) in D <tex>helper(e_{j}) \leftarrow v_i</tex>===== Корректность ====={{Лемма

Если на шаге Функция ''MakeMonotone(1P) построения последовательности триангуляции удалять несмежные вершины со степенью меньше некоторого целого (будет указано позже) числа $K$'' корректно выполняет разбиение многоугольника <tex>P</tex>. Другими словами эта функция добавляет в <tex>P</tex> множество непересекающихся диагоналей, то свойства, описанные выше, будут выполненыкоторые разбивают <tex>P</tex> на монотонные части.|proof=Тот факт, что <tex>P</tex> разбивается на монотонные части следует из предыдущей леммы.Остаётся доказать, что диагонали, построенные в процессе выполнения алгоритма, попарно не пересекаются и не пересекают стороны <tex>P</tex>.  Рассмотрим случай выполнения функции ''HandleSplitVertex'1', поскольку это наиболее общий случай: split вершина может быть соединена со всеми типами вершин, в отличие от остальных функций (в них рассматриваемая в данный момент вершина может быть соединена только с merge вершиной).  Допустим, что диагональ <tex>v_{i}v_{m}</tex> была построена с помощью ''HandleSplitVertex' Для проверки первого свойства воспользуемся некоторыми особенностями плоских графов' по достижению split вершины <tex>v_i</tex>. Рассмотрим четырёхугольник <tex>H</tex>, заключённый между <tex>e_j</tex> и <tex>e_k</tex> - левым и правым ребром относительно <tex>v_i</tex> и горизонтальными прямыми, проведёнными через <tex>v_i</tex> и <tex>v_m</tex>. Внутри <tex>H</tex>, не может находиться ни одной из вершин <tex>P</tex>, в противном случае <tex>helper(e_j)</tex> не равнялся бы <tex>v_m</tex>. Предположим теперь, что <tex>v_{i}v_{m}</tex> пересекает <tex>e_s</tex> одну из сторон <tex>P</tex>. Учитывая, что никаких вершин <tex>P</tex> не лежит внутри <tex>H</tex> и стороны <tex>P</tex> не пересекаются, то <tex>e_s</tex> должна пересечь либо отрезок, соединяющий <tex>e_j</tex> и <tex>v_m</tex>, либо <tex>e_j</tex> и <tex>v_i</tex>. Из [[Формула_Эйлера Файл:Pic_of_correctness.jpg‎| формулы Эйлера400px|thumb|right|1) Вершин внутри <tex>H</tex> находиться не может; 2) <tex>v_{i}v_m</tex> может пересекать только рёбра, помеченные зелёным]] для плоских графов, Такое возможно только в частном случае триангуляции, ограниченной тремя ребрами, следуеткогда точками пересечения будут являться <tex>v_i</tex> или <tex>v_m</tex>, что число не противоречит условию. Отсюда <tex>v_{i}v_{m}</tex> не пересекает ни одну из сторон <tex>P</tex> в посторонних точках.  Теперь рассмотрим случай с пересечением добавленной ранее диагональю. Поскольку внутри <tex>H</tex> никаких вершин вершин $N$ находиться не может, и число ребер $e$ связаны соотношением оба конца любой добавленной ранее диагонали должны лежать выше <tex>v_i</tex>, диагональ <tex>v_{i}v_m</tex> не может пересекать никакую из ранее добавленных диагоналей.}}===== Оценка работы =====Построение описанной выше приоритетной очереди <tex>Q</tex> происходит за линейное время. Когда заметающая прямая останавливается в вершине: операции с очередью занимают константу по времени, операции с деревом <tex>T</tex> на запросы и обновления требуют <tex>\mathcal{O}(\mathcal \log n)</tex>. Добавление диагонали в <tex>D</tex> требует <tex>\mathcal{O}(1)</tex>. В итоге обработка каждой вершины требует <tex>\mathcal{O}(\log n)</tex>, а весь алгоритм соответственно <tex>\mathcal{O}(n \log n)</tex>. Что касается памяти, она очевидно составляет <tex>\mathcal{O}(n) </tex>. Очередь <tex>Q</tex> и дерево <tex>T</tex> занимают линейную память. [[Файл:Triangulationg intro.jpg|170px|thumb|right|Зелёным помечена так называемая воронка, которая образуется, когда мы достигнем красной вершины]] $e = 3N = Триангуляция монотонного многоугольника ==Будем проходить сверху вниз по вершинам многоугольника проводя диагонали где это возможно. Отсортируем все вершины многоугольника <tex>P</tex> в порядке убывания их <tex>y</tex>- 6$координаты.Пока Заведём стек вершин <tex>S</tex>. В стеке будем хранить вершины в триангнуляции отсортированном порядке, которые были обработаны, но не были отрезаны от многоугольника, то есть внутренние находятся в той части многоугольника, которая ещё не была триангулирована. В момент обработки некоторой вершины, будем пытаться провести из неё как можно больше диагоналей к вершинам, содержащимся в стеке. Эти диагонали отрезают треугольники от <tex>P</tex>. На вершине стека будет храниться вершина, которая будет обрабатываться последней. Часть многоугольника <tex>P</tex>, лежащая выше последней обработанной вершины <tex>v_i</tex> и которая ещё не была триангулирована имеет форму перевёрнутой воронки (в противном случае задача тривиальнасм. рисунки). Одна сторона воронки состоит из одной из сторон <tex>P</tex>, степень каждой а другая состоит из трех граничных цепи вершин , которые лежат выше <tex>v_i</tex> и внутренние углы которых не меньше трех<tex>\pi</tex>. Поскольку существует $3N - 6$ реберНесложно догадаться, что самая нижняя вершина стека является единственной выпуклой. Несложно также заметить, а каждое ребро инцидентно двум вершинамчто при обработке следующей вершины свойство перевёрнутой воронки сохранится, то сумма степеней всех есть оно является инвариантом алгоритма. [[Файл:Triang_alg_case1.jpg|200px|thumb|left|Первый случай. Синим помечены стороны воронки, зелёным — диагонали, а жёлтым границы новой ещё не протриангулированной области]][[Файл:Triang alg case2.jpg|300px|thumb|right|Второй случай. Синим помечена цепь из вершин меньше $6N$, которая содержится в стеке <tex>S</tex> на момент достижения вершины <tex>v_j</tex>, рыжей помечена первая вершина, до которой невозможно провести диагональ, жёлтой помечена новая нетриангулированная область <tex>P</tex> в форме воронки]]=== Алгоритм ===Рассмотрим процесс обработки вершины более подробно. Возможны два случая:* Текущая вершина <tex>v_j</tex> является нижним концом стороны <tex>e</tex>, ограничивающего воронку. Вершины противоположной цепи уже были положены в стек. В этом случае можно просто построить диагонали, соединяющие <tex>v_j</tex> со всеми вершинами, находящимися в стеке, кроме последней. Последняя вершина в стеке уже соединена с <tex>v_j</tex> стороной <tex>e</tex>. Отсюда сразу следуетЧасть многоугольника <tex>P</tex>, лежащая выше <tex>v_j</tex>, что которая не менее $ \fracбыла триангулирована, ограничена диагональю, которая соединяет <tex>v_j</tex> с вершиной <tex>v_{Ns1}</tex>, которая была первой в стеке. Сторона многоугольника <tex>P</tex>, выходящая из <tex>v_{2s1}$ вершин имеет степень меньше 12</tex> направлена вниз. СледовательноСнова образуется фигура c одним выпуклым углом, пусть $K = 12$похожая на воронку — инвариант сохраняется. Пусть также $v$ Вершины <tex>v_j</tex> и <tex>v_{s1}</tex> кладутся в стек, поскольку они были были обработаны, но по прежнему являются вершинами непротриангулированной части <tex>P</tex>. * Вершина <tex>v_j</tex> принадлежит последовательной цепи вершин, добавленных в <tex>S</tex>. Вынем из стека верхнюю вершину <tex>v_{---s1}</tex> — она уже соединена с <tex>v_{j} число выбранных вершин</tex> одной из сторон <tex>P</tex>. Поскольку каждой Затем будем пытаться выстраивать диагонали, соединяющие <tex>v_{j}</tex> c вынимаемыми из них инцидентно не более $K-1 = 11$ реберстека вершинами пока это возможно. Проверку на возможность построения диагонали <tex>v_{j}v_{k}</tex>, где <tex>v_{k}</tex> — текущая верхняя вершина стека, а три граничные можно осуществлять посредством изучения взаимного расположения предыдущей вершины не выбираются, то вынутой из <tex>S</tex>, относительно <tex>v_{j}v_{k}</tex>. Когда мы имеем $v \ge \left \lfloor \fracдостигнем вершины <tex>v_{k}</tex>, до которой невозможно провести диагональ, положим предыдущую вершину <tex>v_{k-1}</tex> обратно в стек. Вершина <tex>v_{12k-1}(\frac</tex> является либо последней, до которой было возможно провести диагональ, либо, если ни одной диагонали из <tex>v_{j}</tex> провести не удалось, — соседом <tex>v_{Nj}</tex>. Далее положим <tex>v_{2j} </tex> в стек. Опять же инвариант непротриангулированной части <tex>P</tex> сохраняется: одна сторона воронки ограничена частью стороны многоугольника, а другая цепью невыпуклых вершин. === Псевдокод ===Как ранее уже было отмечено, задаём <tex>P</tex> в виде рёберного списка c двойными связями <tex>D</tex>. TriangulateMonotonePolygon(P) vertex [n] V = new vertex(P); // массив вершин <tex>P</tex>, отсортированный по y- координате в порядке убывания. stack S = new stack(); S.push(V[1]); S.push(V[2]); for j <tex>\leftarrow</tex> 3to n - 1 if (V[j] = S.peek() ) while (S <tex>\right neq \rfloor $varnothing </tex>) if (S.size() <tex>\neq</tex> 1)Следовательно Insert edge(V[j], $a \cong S.peek()) in D S.pop() S.push(V[j-1 - ]) S.push(V[j]); else vertex last <tex>\frac{1}{24} leftarrow< 0/tex> S.peek(); S.pop(); while (IsValidDiagonal(edge(V[j], S.peek()),959 last)) //проверка возможности построения //диагонали — предикат "левый поворот" last < tex>\leftarrow</tex> S.peek(); S.pop(); Insert edge(V[j], last) in D S.push(last); S.push(V[j]); S.pop() while (S <tex>\neq \varnothing </tex>) if (S.size() <tex>\neq</tex> 1$) Insert edge(V[j], S.peek()) in D S.pop()=== Корректность ===* Все построенные диагонали попарно не пересекаются. Это гарантируется тем, что доказывает справедливость свойства 1при каждом просмотре определённой вершины рассматривается только та часть <tex>P'</tex> многоугольника <tex>P</tex>, которая не была протриангулирована, следовательно внутри этой области по определению не может лежать ни одной из уже построенных диагоналей. Несложно заметить, что в стеке <tex>S</tex> на каждой итерации главного цикла хранятся вершины, которые принадлежат именно <tex>P'</tex> и лежат выше рассматриваемой вершины.* Количество построенных диагоналей всегда будет <tex>n-3</tex>, поэтому непротриангулированных частей в многоугольнике не останется.=== Оценка работы ===Построение массива вершин требует линейное время и занимает линейную память. Главный цикл ''for'2' выполняется <tex>n-3</tex> раза. Каждая его итерация может потребовать линейное время. Однако заметим, что на каждой итерации главного цикла в стек кладутся максимум две вершины, следовательно общее число выполнения операции ''push' Выполнение второго свойства обеспечивается тривиально. Поскольку удаление ', включая первые две вершины со степенью меньше $K$ приводит к образованию многоугольника с числом ребер менее $K$, то каждый из удаленных треугольников пересекает положенные в начале алгоритма, ограничено <tex>2n-4</tex>. Количество операций ''pop'' за время работы алгоритма не более $K - 2 превысит количества операций ''push''. Отсюда общее время работы цикла ''for'' <tex>\mathcal{O}(n)</tex>. В итоге общее время работы <tex>\mathcal{O}(n)</tex>.=== Общая оценка === H$ новых треугольниковРазбиение многоугольника на монотонные части занимает <tex>\mathcal{O}(n \log n)</tex> времени и <tex>\mathcal{O}(n)</tex> памяти. Триангуляция каждой из частей занимает линейную память и время.Учитывая то, что суммарное количество вершин во всех частях <tex>\mathcal{O}(n)</tex>, триангуляция всех частей займёт <tex>\mathcal{O}(n)</wikitextex>по времени и по памяти.

===Поиск===В итоге общая оценка составляет <wikitextex>После построения структуры легко понять, как в ней происходит поиск. Элементарной операцией здесь является определение принадлежности треугольнику. Очевидно, что она выполняется константное время. Сначала мы локализуемся в треугольнике $S_1$. После этого мы строим путь от корневой вершины до листа следующим образом: находясь в какой-либо вершине $z$, просмотрим всех ее детей на принадлежность точки соответствующему треугольнику и, так как точка может находиться лишь в одном треугольнике конкретной триангуляции, перейдем в эту вершину, и продолжим поиск.Этот поиск также можно рассматривать как последовательную локализацию в триангуляциях $S_1, \dots, S_mathcal{hO}(Nn \log n)}$, откуда и происходит название самого метода.</wikitextex>====Псевдокод====по времени и <wikitextex>Пусть все потомки узла $u$ из $T$ собраны в список successors(u), а triangle\mathcal{O}(un) обозначает треугольник, соответствующий узлу $u$. Тогда алгоритм поиска может выглядеть следующим образом: </wikitextex> procedure localization(z) if (z not in triangle(root)) z in infinite region else u = root while (successors(u) != null) for (v in successors(u)) if (z in triangle(v)) u = v return uпо памяти.