=== Монотонный метод ===Есть множество точек на плоскости. Нужно найти две самые удалённые из них.
[[Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull|Найдём выпуклую оболочку]] исходного множества и получим более простую задачу: найти две наиболее удалённые вершины в выпуклом многоугольнике. Сделать это можно за линейное время с помощью метода, который называется '''вращающиеся калиперы''' (англ. ''rotating calipers'').
''Обоснование: Пусть диаметр с одной стороны содержит точку, которая не принадлежит выпуклой оболочке. Тогда продлим диаметр в эту сторону до пересечения с выпуклой оболочкой. Очевидно, он станет длиннее. А потом заметим, что диаметр станет еще больше, если сдвинуть его к одному из концов ребра, в которое мы уперлись. Конец.''
== Постановка задачи ==
Пусть <tex>P = (p_1, p_2, ... ,p_n)</tex> {{---}} выпуклый многоугольник, в котором порядок обхода вершин направлен против часовой стрелки, и никакие три последовательные точки не лежат на одной прямой. Найти пару чисел <tex>\langle i, j \rangle</tex>, такие, что <tex>d(p_i, p_j)</tex> максимально.
== Вращающиеся калиперы ==
=== Опорные прямые ===
{{Определение
|id=def_monotone_polygon
|definition=
Простой многоугольник Прямая <tex>PL</tex> называется '''монотоннымопорной прямой''' (англ. ''line of support'' относительно прямой ) для многоугольника <tex>lP</tex>, если любая его внутренность лежит по одну сторону от <tex>l'L</tex>, такая что при этом <tex>l' \perp lL</tex>, пересекает стороны проходит хотя бы через одну из вершин <tex>P</tex> не более двух раз (результатом пересечения <tex>l'</tex> и <tex>P</tex> может быть только один отрезок или точка).
}}
{|border=0 width="100%"|{Определение{Теорема|definitionstatement=МногоугольникПусть <tex>L_1</tex> и <tex>L_2</tex> {{---}} две параллельные опорные прямые фигуры <tex>\Phi</tex>, монотонный относительно расстояние между которыми имеет максимальное значение. <tex>A_1</tex> и <tex>yA_2</tex>{{-оси называется '--}} граничные точки фигуры <tex>\Phi</tex>, принадлежащие соответственно прямым <tex>L_1</tex> и <tex>L_2</tex>. Тогда отрезок <tex>A_1A_2</tex> перпендикулярен обеим прямым <tex>L_1</tex> и <tex>L_2</tex>.|proof=Предположим, что это не так. Тогда расстояние между прямыми <tex>L_1</tex> и <tex>L_2</tex> было бы меньше, чем отрезок <tex>A_1A_2</tex>, и тем более меньше, чем расстояние между двумя опорными прямыми <tex>L'_1</tex> и <tex>L'_2</tex> фигуры <tex>\Phi</tex>, перпендикулярными к отрезку <tex>yA_1A_2</tex>-монотонным''', что противоречит условию.
}}
|[[Файл:perpendicular.png|250px|thumb|right]]
|}
Так как <tex>A_1</tex> и <tex>A_2</tex> {{---}} какие угодно граничные точки фигуры <tex>\Phi</tex>, принадлежащие соответственно прямым <tex>L_1</tex> и <tex>L_2</tex>, то из перпендикулярности отрезка <tex>A_1A_2</tex> к прямым <tex>L_1</tex> и <tex>L_2</tex> следует, что ни одна из прямых <tex>L_1</tex>, <tex>L_2</tex> не может иметь с фигурой <tex>\Phi</tex> целый общий отрезок. Другими словами, каждая из этих прямых содержит единственную граничную точку фигуры <tex>\Phi</tex>.
Суть данного метода заключается в том, чтобы разбить многоугольник на монотонные части, а затем триангулировать каждую из них.=== Разбиение многоугольника на монотонные части =={| border="0" width="100%"[[Файл: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> \phi > \pi </tex>* '''''end вершина''''' — два её соседа лежат выше её самой и <tex> \phi < \pi </tex>* '''''merge вершина''''' — два её соседа лежат выше её самой и <tex> \phi > \pi </tex>* '''''regular вершина''''' — не является поворотной, в отличие от остальных, другими словами один её сосед находится выше, а другой ниже её самой. {{ЛеммаТеорема
|statement=
Многоугольник <tex>P</tex> является <tex>y</tex>-монотонным, если в нём отсутствуют split и merge вершиныДиаметр выпуклого многоугольника равен максимальному расстоянию между параллельными опорными прямыми.
|proof=
ПредположимПусть <tex>\Phi</tex> {{---}} выпуклая фигура, что <tex>PL_1</tex> не и <tex>yL_2</tex>{{--монотонный. Тогда докажем-}} параллельные опорные прямые, что расстояние между которыми имеет наибольшее возможное значение <tex>Pd</tex> содержит split и merge вершины. Поскольку , <tex>PA_1</tex> не и <tex>yA_2</tex>{{---монотонный, существует горизонтальная прямая }} общие точки фигуры <tex>l\Phi</tex>, которая пересекает его стороны более двух раз. Выберем и прямых <tex>lL_1</tex> таким образом, чтобы самой левой компонентой пересечения и <tex>lL_2</tex> и соответственно. По предыдущей теореме <tex>PA_1A_2</tex> был бы отрезок перпендикулярен к прямым <tex>pqL_1</tex>. Далее будем двигаться наверх по сторонам , <tex>PL_2</tex>, начиная от точки следовательно, его длина равна <tex>qd</tex>. В результате в некоторой точке Докажем, что расстояние между любыми двумя точками фигуры <tex>r\Phi</tex>, где не преводходит <tex>r \neq pd</tex> (случай '''(a)''' на рисунке). Действительно, прямая если <tex>lB</tex> снова пересечёт одну из сторон и <tex>PC</tex>. Отсюда самая высокая точка, которую мы достигли во время движения по сторонам {{---}} какие-либо две точки фигуры <tex>P\Phi</tex>, будет split вершиной. [[Файл:Proof_lemma.jpg|450px]] Если же а <tex>r = pm</tex> (случай '''(b)''' на рисунке), начём опять двигаться по сторонам и <tex>Pn</tex> теперь уже вниз. Как и в предыдущем случае найдётся некоторая точка {{---}} опорные прямые, перпендикулярные к отрезку <tex>r'BC</tex>, которая будет результатом пересечения то отрезок <tex>lBC</tex> и не превосходит расстояния между прямыми <tex>Pm</tex>. При этом и <tex>r' \neq pn</tex>, которое в противном случае свою очередь не превосходит <tex>ld</tex> будет пересекать . Следовательно, длина <tex>PBC</tex> только два раза, что противоречит выбору не может быть больше <tex>ld</tex>. Аналогично предыдущему случаю, выберем теперь самую низкую точку, которую мы достигли во время движения по сторонам P. Она будет merge вершиной.
}}
|[[Файл:max_parallel.png|170px|thumb|right]]|}
=== Алгоритм ===
Чтобы сделать многоугольник монотоннымЗаметим, нужно избавиться от split и merge вершин путём проведения непересекающихся дигоналей из таких вершинчто параллельные опорные прямые можно провести не через любую пару точек.
Рассмотрим горизонтальную заметающую прямую <tex>l</tex>, будем перемещать её сверху вниз вдоль плоскости на которой лежит исходный многоугольник <tex>P</tex>. Будем останавливать её в каждой вершине многоугольника. В тот момент, когда на пути заметающей прямой встречается split или merge вершина её нужно соединить с вершиной, у которой расстояние до <tex>l</tex> минимально, при этом она должна лежать соответственно выше или ниже <tex>l</tex>.{{Определение[[Файл:Split_case.jpg|200px|thumb|right|Обработка ''split'' вершины <tex>v_i</tex>]] Рассмотрим каждый случай подробнее:definition= # '''''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 вершина'(англ. ''antipodal''. В отличие от случая со split вершиной заранее вычислить указатель <tex>helper</tex> нельзя, поскольку merge вершина <tex>v_i</tex> должна быть соединена с вершиной, лежащей ниже заметающей прямой <tex>l</tex>. Для этого в <tex>helper(e_j)</tex> - левого относительно <tex>v_i</tex> ребра запишем саму <tex>v_i</tex>. Далее спускаем заметающую прямую вниз к следующей вершине <tex>v_m</tex>, обращаемся к <tex>helper</tex>'у её левого ребра. Проверяем, если там хранится merge вершина, строим диагональ <tex>v_{i}v_{m}</tex>. Последняя проверка осуществляется для любого типа вершины, кроме split, согласно п.1.[[Файл:Merge_case_1_2.jpg|500px|thumb|center|Обработка ''merge'' вершины <tex>v_i</tex>. На рисунке слева <tex>v_i</tex> записывается в качестве <tex>helper</tex>'а своего левого ребра. На правом рисунке ближайшая вершина <tex>v_m</tex> при обращении к своему левому ребру <tex>helper(e_j)</tex> находит <tex>v_i</tex> и образует диагональ <tex>v_{i}v_m</tex>]] === Структуры данных ===В подходе, описанном выше, требуется находить пересечения заметающей прямой и левых ребёр многоугольника. Создадим двоичное дерево поиска <tex>T</tex>, в листьях которого будем хранить рёбра, пересекающие <tex>l</tex>, такие, что внутренняя область многоугольника будет лежать справа от них самих. С каждым таким ребром будем хранить его <tex>helper</tex>. Порядок следования листьев в дереве соответствует порядку следования рёбер в многоугольнике: слева направо. Дерево изменяется в зависимости от текущего состояния заметающей прямой. Создадим приоритетную очередь <tex>Q</tex> из вершин, в которой приоритетом будет <tex>y</tex>-координата вершины. Если две вершины имеют одинаковые <tex>y</tex>-координаты, больший приоритет у левой. Вершины будут добавляться на "остановках" заметающей прямой.
Многоугольник <tex>P</tex> и добавленные Благодаря предыдущей теореме нам нужно рассмотреть только противолежащие точки. Задача в процессе диагонали удобно хранить в виде списка <tex>D</tex> рёбер с двойными связями (''DCEL — doubly-connected edge list'')том, так как потом это обеспечит эффективный доступ к каждой из частейчтобы рассмотреть их, которые нужно будет триангулироватьне перебирая все пары точек.
{|border="0" width== Псевдокод ==="100%" MakeMonotone(P) Construct(D); Construct(Q); // функция Construct создаёт объекты |Рассмотрим рисунок справа. <tex>DL</tex> и <tex>QM</tex> {{---}} опорные прямые, описанные выше. bst T = new bst(); while Q проходящие через вершины <tex> \neq \varnothing A</tex> Remove и <tex>v_{max}D</tex> from Q соответственно. Значит, <tex>\langle A,D \rangle<// удаление вершины с наивысшим приоритетом tex> {{---}} противолежащая пара точек. Если начать вращать прямые против часовой стрелки вокруг данных точек, они будут оставаться опорными прямыми, пока одна из прямых не станет накладываться на сторону многоугольника. В нашем примере, при вращении <tex>QM</tex> switch (Type_of_vertex(к позиции <tex>v_{max}M'</tex>)): // определение типа вершины case 'start': HandleStartVertex(, <tex>v_{max}M</tex>); case 'end': HandleEndVertex(коснётся точки <tex>v_{max}E</tex>); case 'split': HandleSplitVertex(раньше, чем <tex>v_{max}L</tex>); case 'merge': HandleMergeVertex(коснётся <tex>v_{max}B</tex>); case 'regular': HandleRegularVertex(, поэтому <tex>v_{max}\langle A,E \rangle</tex>);становится новой парой противолежащих точек.
[[Файл:Split-merge - result.png|470px|thumb|right]] Опишем теперь каждый метод из последнего switch: HandleStartVertex(Теперь <tex>v_{i}M'</tex>) Insert будет вращаться вокруг <tex>e_{i}E</tex> in T , а <tex>helper(e_{i}) \leftarrow v_iL'</tex> HandleSplitVertex(продолжит вращаться вокруг <tex>v_{i}A</tex>) edge <tex>e_j</tex> = , и следующей парой противолежащих точек станет <tex>l \cap P</tex> Search <tex>e_j</tex> in T Insert edge(<tex>v_{i}</tex>langle B, <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}) E \leftarrow v_i</tex> В последующих трех функциях обработки вершины <tex>v_i</tex> происходит обращение к смежному ребру <tex>e_{i-1}rangle</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') 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 |[[Файл:calipers.png|250px|thumb|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>===== Корректность ==Асимптотика ==={{ЛеммаТеорема
|statement=
Функция ''MakeMonotone(P)'' корректно выполняет разбиение многоугольника Представленный выше алгоритм генерирует все пары противолежащих точек в многоугольнике <tex>P</tex>. Другими словами эта функция добавляет в , состоящем из <tex>PN</tex> множество непересекающихся диагоналейвершин, которые разбивают за время <tex>PO(N)</tex> на монотонные части.|proof=Тот факт, что <tex>P</tex> разбивается на монотонные части следует из предыдущей леммы.Остаётся доказать, что диагонали, построенные в процессе выполнения алгоритма, попарно не пересекаются и не пересекают стороны <tex>P</tex>. Рассмотрим случай выполнения функции ''HandleSplitVertex'', поскольку это наиболее общий случайДанный алгоритм можно реализовать следующим образом: 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> никаких вершин вершин находиться не может, и оба конца любой добавленной ранее диагонали должны лежать выше <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|Зелёным помечена так называемая воронка, которая образуется, когда мы достигнем красной вершины]]
== Триангуляция монотонного многоугольника ==
Будем проходить сверху вниз по вершинам многоугольника проводя диагонали где это возможно.
Отсортируем все вершины многоугольника <tex>P</tex> в порядке убывания их <tex>y</tex>-координаты. Заведём стек вершин <tex>S</tex>. В стеке будем хранить вершины в отсортированном порядке, которые были обработаны, но не были отрезаны от многоугольника, то есть находятся в той части многоугольника, которая ещё не была триангулирована. В момент обработки некоторой вершины, будем пытаться провести из неё как можно больше диагоналей к вершинам, содержащимся в стеке. Эти диагонали отрезают треугольники от <tex>P</tex>. На вершине стека будет храниться вершина, которая будет обрабатываться последней.
Часть многоугольника <tex>P</tex>, лежащая выше последней обработанной вершины <tex>v_i</tex> и которая ещё не была триангулирована имеет форму перевёрнутой воронки (см. рисунки). Одна сторона воронки состоит из одной из сторон <tex>P</tex>, а другая состоит из цепи вершин, которые лежат выше <tex>v_i</tex> и внутренние углы которых не меньше <tex>\pi</tex>. Несложно догадаться, что самая нижняя вершина стека является единственной выпуклой. Несложно также заметить, что при обработке следующей вершины свойство перевёрнутой воронки сохранится, то есть оно является инвариантом алгоритма.
[[Файл:Triang_alg_case1.jpg|200px|thumb|left|Первый случай. Синим помечены стороны воронки, зелёным — диагонали, а жёлтым границы новой ещё не протриангулированной области]]
[[Файл:Triang alg case2.jpg|300px|thumb|right|Второй случай. Синим помечена цепь из вершин, которая содержится в стеке <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>, которая не была триангулирована, ограничена диагональю, которая соединяет <tex>v_j</tex> с вершиной <tex>v_{s1}</tex>, которая была первой в стеке. Сторона многоугольника <tex>P</tex>, выходящая из <tex>v_{s1}</tex> направлена вниз. Снова образуется фигура c одним выпуклым углом, похожая на воронку — инвариант сохраняется. Вершины <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 вынимаемыми из стека вершинами пока это возможно. Проверку на возможность построения диагонали <tex>v_{j}v_{k}</tex>, где <tex>v_{k}</tex> — текущая верхняя вершина стека, можно осуществлять посредством изучения взаимного расположения предыдущей вершины, вынутой из <tex>S</tex>, относительно <tex>v_{j}v_{k}</tex>. Когда мы достигнем вершины <tex>v_{k}</tex>, до которой невозможно провести диагональ, положим предыдущую вершину <tex>v_{k-1}</tex> обратно в стек. Вершина <tex>v_{k-1}</tex> является либо последней, до которой было возможно провести диагональ, либо, если ни одной диагонали из <tex>v_{j}</tex> провести не удалось, — соседом <tex>v_{j}</tex>. Далее положим <tex>v_{j}</tex> в стек. Опять же инвариант непротриангулированной части <tex>P</tex> сохраняется: одна сторона воронки ограничена частью стороны многоугольника, а другая цепью невыпуклых вершин.
=== Псевдокод =Ссылки ==Как ранее уже было отмечено, задаём <tex>P</tex> в виде рёберного списка c двойными связями <tex>D</tex>* ''M.I. TriangulateMonotonePolygon(P) vertex [n] V = new vertex(P); // массив вершин <tex>P</tex>Shamos'' Computational geometry, отсортированный по y1978 {{-координате в порядке убывания. stack S = new stack(); S.push(V[1]); S.push(V[2]); for j <tex>\leftarrow</tex> 3 to n - 1 if (V[j] = S.peek()) while (S <tex>\neq \varnothing </tex>) if (S.size() <tex>\neq</tex> 1) Insert edge(V[j], S.peek()) in D S.pop() S.push(V[j-1]) S}} С.push(V[j]); else vertex last <tex>\leftarrow</tex> S76.peek(); S* ''Яглом И.pop(); while (IsValidDiagonal(edge(V[j], SМ.peek()), last)) //проверка возможности построения //диагонали — предикат "левый поворот" last <tex>\leftarrow</tex> SБолтянский В.peek(); SГ.pop(); Insert edge(V[j]'' Выпуклые фигуры, last) in D S.push(last); S.push(V[j]); S1951 {{---}} С.pop() while (S <tex>\neq \varnothing </tex>) if (S.size() <tex>\neq</tex> 1) Insert edge(V[j]20, S144.peek()) in D S.pop()=== Корректность ===* Все построенные диагонали попарно не пересекаются. Это гарантируется тем, что при каждом просмотре определённой вершины рассматривается только та часть <tex>P'<[https:/tex> многоугольника <tex>P</tex>, которая не была протриангулирована, следовательно внутри этой области по определению не может лежать ни одной из уже построенных диагоналейgithub. Несложно заметить, что в стеке <tex>S</tex> на каждой итерации главного цикла хранятся вершины, которые принадлежат именно <tex>P'<com/tex> и лежат выше рассматриваемой вершины.* Количество построенных диагоналей всегда будет <tex>n-3<Megabyte777/tex>, поэтому непротриангулированных частей в многоугольнике не останется.=== Оценка работы ===Построение массива вершин требует линейное время и занимает линейную память. Главный цикл ''for'' выполняется <tex>n-3<cg/tex> раза. Каждая его итерация может потребовать линейное время. Однако заметим, что на каждой итерации главного цикла в стек кладутся максимум две вершины, следовательно общее число выполнения операции ''push'', включая первые две вершины, положенные в начале алгоритма, ограничено <tex>2n-4<blob/tex>. Количество операций ''pop'' за время работы алгоритма не превысит количества операций ''push''. Отсюда общее время работы цикла ''for'' <tex>\mathcal{O}(n)<master/tex>. В итоге общее время работы <tex>\mathcal{O}(n)<include/tex>.=== Общая оценка ===Разбиение многоугольника на монотонные части занимает <tex>\mathcal{O}(n \log n)<cg/tex> времени и <tex>\mathcal{O}(n)<operations/tex> памятиdiameter. Триангуляция каждой из частей занимает линейную память и время. Учитывая то, что суммарное количество вершин во всех частях <tex>\mathcal{O}(n)</tex>, триангуляция всех частей займёт <tex>\mathcal{O}(n)</tex> по времени и по памятиh Реализация - Github.com]
В итоге общая оценка составляет <tex>\mathcal{O}(n \log n)</tex> по времени и <tex>\mathcal{O}(n)</tex> по памяти.[[Категория: Вычислительная геометрия]]