Изменения

{{nohate}}4 Алгоритм K*== Определение =={{Определение|definition='''Подразбиение Делоне множества точек''' — такое разбиение выпуклой оболочки множества точек Также как и алгоритм Eppstein, K* выполняет поиск пути на множество выпуклых фигурграфе G и использует граф путей P(G). Граф путей ищется с помощью алгоритма Дейкстры для того, что чтобы пути s-t в окружности, описанной вокруг любой из фигурвиде последовательности запасных путей. Общий принцип работы алгоритма K* следующий:1) K* применяет A* на графе G вместо обратного алгоритма Дейкстры, не находится никаких точек из множествакоторый использует алгоритм Eppstein.}}{{Определение|definition='''Триангуляция Делоне множества точек''' — триангуляция2) Мы запускаем A* на G и Дейкстру на P(G) поочередно порядке, являющаяся подразбиением Делонекоторый позволяет Дейкстре доставить пути решение до заверешения поиска на G алгоритма A*.}}

== Существование триангуляции Делоне =={{Лемма|about=4.1Поиск A* на G. |statement=K* применяет A* к входному графу G для того, чтобы определить дерево поиска T. Окружность, спроецированная на параболоид, находится В отличие от алгоритма Eppstein в K* A* применяется к графу G в одной плоскостипрямом порядке из-за чего коренем дерева T является вершина s. Все точкиЭто необходимо для того, лежащие внутри окружностичтобы была возможность работать c неявным описанием графа G через функцию successor. На протяжении статьи будем считать граф G конечным, будут лежать под этой плоскостьюесли не будет сказано иначе. ТочкиЗаметим, лежащие вне окружностичто А* корректен на конечных графах. Будем следовать литературному соглашению, будут лежать над плоскостью.}}{{Теорема|statement=Подразбиение Делоне существуетпредполагая, причём для каждого набора точек оно единственно.|proof=Спроецируем все точки на параболоид и построим выпуклую оболочкучто стоимость бесконечного пути неограниченна.

Все грани выпуклой оболочки окажутся внутри параболоида 4.2 Стоимость объездаДля ребра (u, v) стоимость объезда \delta(u, v) является стоимостью ущерба из-за его выпуклостивзятия ребра объезда (u, v) в сравнении с кратчайшим путем s-t через v. При этом точки лежат на параболоидеНи длина кратчайшего пути s-t через v, ни длина пути s-t, включающего запапасные ребра (u, v) не известны, когда A* обнаруживает (u, v). Поэтому не найдётся точекОбе длины могут быть оценены с помощью функции оценки f, которые будут лежать за гранями выпуклой оболочкикоторая использует эвристическую функцию h. То есть все точкиПуть f(v) будет f-значением с соответствии с деревом поиска T и f_u(v) будет f-значанием в соответствии с родителем u, спроецированные на параболоидт.е. f_u(v) = g(u) + c(u, будут принадлежать выпуклой оболочкеv) + h(v).\delta(u, v) может быть определена так: \delta(u, v) = f_u(v) - f(v) = g(u) + c(u, v) + h(v) - g(v) - h(v) = g(u) + c(u, v) - g(v)

По лемме 1 очевидноЗаметим, что внутри окружностей\delta(u, описанных вокруг проекций граней выпуклой оболочкиv) дает точную объездную метрику, поскольку функция оценки h-значения не будет лежать никаких точек. Значитпоявляется в определении функции \delta(u, проекции граней — фигуры подразбиения Делоне. Значит, такое подразбиение существуетv).

Из единственности выпуклой оболочки следует4.3 Структура графе путейСтруктура графа путей P(G) довольно сложная. В принципе, P(G) будет ориентированным графом, вершины которого соответствуют ребрам в исходном графе G. Он будет организован как коллекция взаимосвязанных куч (англ. heap). 2 бинарные минимальные кучи присвоены к каждой вершине v в графе G, которые называются входящей кучей H_{in}(v) и деревянной кучей H_{T}(v). Эти кучи являются базисом P(G). Как мы покажем далее, испльзование этих куч также играет главную роль в поддержании асимптотической сложности K*, что такое подразбиение единственнотакже как в EA и LVEA.Входящая куча H_{in}(v) содержит узлы для каждого запасного ребра к вершине v, которые до сих пор были обнаружены A*. Узлы H_{in}(v) будут упорядочены в соответствии с \delta-значением соответствующих переходов. Узел владеющий ребром с минимальной стоимостью ущерба будет расположен на вершине кучи. Мы ограничим структуру кучи H_{in}(v) таким образом, что её корень в отличие от остальных узлов, имеет не более 1 ребенка. Мы обозначим его root_{in}(v).

== Критерий Делоне Деревянная куча H_{T}(v) для рёбер произвольной вершины v строится следующим образом. Если v - стартовая вершина, т.е. v==s, то H_{T}(v) будет изначально пустой кучей. Затем узел в неё будет добавлен root_{Определение|definition='''Критерий Делоне для ребра''': на ребре можно построить такую окружностьin}(s), что внутри неё если H_{in}(s) не пустая. Если v не стартовая вершина, то пусть вершина u будет лежать никаких точекродителем вершины v в дереве поиска T.Мы можем представить, что H_{T}(v) конструируется как копия H_{T}(u), в которую добавлен root_{in}(v). Если H_{in}(v) пустая, то H_{T}(v) идентична H_{Лемма|about=2|statement=Триангуляции Делоне принадлежат те и T}(u). Однако, для экономии памяти мы создаем только те рёбра дешевую копию H_{T}(с поправкой на точкиu). Это осуществляется через создание копий только узлов кучи, лежащие которые лежат на одной окружностиобновленном пути H_{T}(u), которые удовлетворяют критерию Делоне.|proof=[[Файл:Good edgesОставшаяся часть H_{T}(u) не копируется.png|200px|right]]ТоДругими словами, root_{in}(v) вставляется в H_{T}(u) неразрушающим путем так, что для рёберструктура H_{T}(u) сохраняется. В куче H_{T}(v) 1 или 2 ребенка могут быть присоединены к root_{in}(v). К тому же, принадлежащих триангуляции Делоне, выполняется критерий Делоне для рёбер, очевидно root_{in}(v) хранит только 1 собственного ребенка из H_{in}(v). Мы обозначим корень H_{T}(v) как R(вокруг каждого ребра можно описать окружность, проходящую через противолежащую ему точку в смежном треугольнике, причём в окружности не будет никаких точек по критерию Делонеv).

ДокажемОбратимся к ребрам, что если которые берут начало из входящих или деревянных куч, как к кучным ребрам. Сформулируем следующую лемму.Лемма 1. Все узлы, которые достижимы из R(v) через кучные ребра для ребра выполняется критерий Делонекаждой вершины v, формируют тернарную кучу, то оно принадлежит триангуляции Делонеупорядоченную в соответствии с \delta-значением. Мы назовем такую кучу графовой кучей вершины v и обозначим его как H_{G}(v).

Предположим, что это ребро (назовём его <tex>AB</tex>) не принадлежит триангуляции Делоне. Тогда существует пересекающее его ребро <tex>CD</tex>, принадлежащее триангуляции. Рассмотрим четырёхугольник <tex>ACBD</tex>. Точки <tex>C</tex> и <tex>D</tex> лежат вне окружности, построенной на <tex>AB</tex> как на хорде, поэтому сумма углов <tex>C</tex> и <tex>D</tex> меньше 180°. Аналогичным образом доказывается, что сумма углов <tex>A</tex> и <tex>B</tex> тоже меньше 180°. Значит, сумма углов четырёхугольника <tex>ACBD</tex> меньше 360°, что невозможно. Противоречие. Значит, ребро <tex>AB</tex> принадлежит триангуляции Делоне.}}

== Локальный критерий Делоне =={{Определение|definition='''Локальный критерий Делоне''': для пары треугольниковФинальная структура P(G) получется из входящих и деревянных куч следующим образом. К каждому узлу n из P(G), которым принадлежит это несущему ребро, выполняется критерий Делоне (то есть вершинаu, противолежащая ребру в одном треугольникеv), не лежит в окружностимы присоединим указатель, описанной вокруг другогоссылающийся на R(u), и наобороткоторый является корневым узлом H_{T}(u).}}Будем называть '''хорошими''' те рёбраМы назовем такие указатели кросс-ребрами, для которых выполняется локальный критерий Делоне.{{Лемма|about=3|id=fliplemma|statement=Из двух рёберв то время как указатели, которые можно провести для пары треугольниковвозникающие из куч названы кучными ребрами, как минимум одно хорошееупоминалось раньше.|proof=[[Файл:Bad edges.png|200px|right]]ПредположимБолее того, что это не так, то есть оба ребра мы добавим специальный узел R в P(G) с одним выходящим кросс-ребром к R(назовём их <tex>AB</tex> и <tex>CD</tex>t) плохие. Рассмотрим четырёхугольник <tex>ACBD</tex> и окружность, описанную вокруг треугольника <tex>ABC</tex>. Точка <tex>D</tex> лежит внутри этой окружности, значит, сумма углов <tex>C</tex> и <tex>D</tex> больше 180°. Аналогично доказывается, что сумма углов <tex>A</tex> и <tex>B</tex> больше 180°. Значит, сумма углов четырёхугольника <tex>ACBD</tex> больше 360°, что невозможно.}}{{Лемма|about=4|statement=Если для всех рёбер выполняется локальный критерий Делоне, то выполняется и глобальный критерий Делоне.|proof=[[Файл:Bad triangle.png|200px|right]]Пример:Все рёбра треугольника хорошие, но описанная окружность содержит точки.

ПредположимБолее того, что это не так, то есть все рёбра хорошие, но существуют треугольники, описанная окружность которых содержат какие-либо точки триангуляциимы определим весовую функцию \Delta на ребрах из P(G). Возьмём какую-либо конфликтную точку <tex>E</tex>. Рассмотрим такой треугольник <tex>ABC</tex> из техПусть (n, n') обозначает ребро в описанную окружность которых попадает <tex>E</tex>P(G), что угол <tex>BEC</tex> максималени пусть e и e' обозначают ребра из G соответствующие узлам n и n'. Тогда определим \Delta(n, если <tex>BC</tex> — ближайшая к точке <tex>E</tex> сторона. Пусть треугольник <tex>BDC</tex> — смежный с <tex>ABC</tex>.n') следующим образом:

Докажем\Delta(n, что точка <tex>E</tex> лежит в окружности, описанной вокруг <tex>BDC</tex>. Предположим, что это не так. Посмотрим на окружность, описанную вокруг треугольника <tex>ABC</tex>: <tex>n')=\angle BAC + delta(e') - \angle BEC > 180^\circ</tex> и <tex>delta(e) если (n,n') кучное ребро\angle BAC + \angle BDC < 180^\circ</tex>. Если точка <tex>E</tex> не лежит в окружностиDelta(n, описанной вокруг треугольника <tex>BDC</tex>, то <tex>\angle BEC < n')=\angle BDC</tex>delta(e') если (n, что противоречит предыдущим двум неравенствамn') кросс-ребро.

ОчевидноЛемма 1 подразумевает, что угол <tex>BED</tex> большекуча упорядоченная в соответствии с \delta-значанием поддерживается по любому кучному ребру из P(G). Эта упорядочивание кучи подразумевает, что \Delta(n,n') неотрицательна для любого кучного ребра (n, чем угол <tex>BEC</tex>n'). При этом точка <tex>E</tex> лежит в окружностиСледовательно, \Delta также неотрицательна, описанной вокруг <tex>BDC</tex>т.е. Значит\Delta(n, при выборе треугольника нужно было взять не <tex>ABC</texn') >= 0 для любого ребра (n,n') в P(G). Стоимость пути \sigma, а <tex>BDC</tex>т. Противоречиее.C_{P(G)}(\sigma) равна \sum_{e \in \sigma}\Delta(e).

== Динамическая триангуляция =={{Определение|definition=Рассмотрим пару смежных треугольников. Рёбра этих треугольников образуют четырёхугольник с проведённой в нём диагональю. Операция замены этой диагонали на другую называется '''flip''' ('''флип''').}}[[Файл:Flip.png|200px|thumb|right|Красное ребро — до флипа, синее — после]]Из [[#fliplemma|леммы 3]] следует, что если ребро плохое, то флип сделает его хорошим.{{Лемма|about=5|statement=Флип плохого ребра уменьшает разность объёмов параболоида и триангуляции, спроецированной на него.|id=volumelemma|proof=Рассмотрим два таких смежных треугольника, что ребро между ними является плохим. Спроецируем их на параболоид. Четыре точки, принадлежащие смежным треугольникам, при проекции на параболоид образуют тетраэдр.

Проведём через Лемма 2. Пусть n будет узлов графовой кучи H_{G}(w) для какой-нибудь из двух треугольников плоскостьвершины w. Вершина, противолежащая основанию тетраэдра, являющегося этим треугольникомПусть (u, лежит ниже этой плоскости (так как не выполняется локальный критерий Делонеv), то есть тетраэдр лежит ниже тела, образующегося при проекции всей триангуляции на параболоидбудет ребром связанным с n. Тогда существует путь в дереве поиска T из v в w.

После флипа станет выполняться локальный критерий Делоне, то есть тело станет включать в себя тетраэдр. Поэтому после флипа плохого ребра объём тела увеличится на объём этого тетраэдра.}}{{Лемма|about=6|statement=Флипами можно достичь хорошей триангуляции за конечное время.|proof=Всего триангуляций заданного множества точек конечное число, и среди них есть триангуляция Делоне. Последовательность флипов плохих рёбер триангуляции образует такую последовательность триангуляций, что разность объёмов параболоида и спроецированной на него триангуляции убывает ([[#volumelemma|по лемме 5]]). Эта последовательность конечна (при этом последней в последовательности является триангуляция Делоне), значит, число флипов, требуемых для достижения триангуляции Делоне, тоже конечно.}}{{Лемма|about=7|statement=Если в триангуляцию Делоне вставить точку в некоторый треугольник и соединить его вершины с этой точкой, то получившиеся рёбра будут хорошими.|id=newedgeslemma|proof=[[Файл:Good edge.png|200px|thumb|right|Точка V вставлена в треугольник ABC]]Предположим, точка была вставлена не на ребро. Рассмотрим любое из рёбер — пусть это будет ребро <tex>VC</tex>. Проведём окружность, описывающую треугольник <tex>ABC</tex>. По критерию Делоне в ней не будет никаких точек триангуляции. На ребре <tex>VC</tex> можно построить окружность, изнутри касающуюся окружности, описанной вокруг треугольника. В ней тоже нет никаких точек. Значит, для <tex>VC</tex> выполняется критерий Делоне для рёбер, значит, ребро должно принадлежать триангуляции с добавленной точкой <tex>V</tex>, значит, оно хорошее.

Случай, когда точка вставляется на ребро, рассматривается аналогично4.4 Алгоритмическая структура K*}}=== Вставка точки ======= Вставка точки, лежащей внутри триангуляции ====[[Файл:Insert in triangleАлгоритмический принцип K* следующий.png|200px|thumb|left|Вставка в треугольник]][[Файл:Insert on edgeБудем запускать алгоритмы Дейкстры и A* на G с чередованием.png|200px|thumb|right|Вставка на ребро]] Для начала локализуемся: поймёмСначала, в каком фейсе лежит точка (или мы запустим A* на каком ребре). Если точка лежит внутри фейса, добавляем три ребра, сам фейс превращаем в один G пока вершина t не будет выбрана из новых смежных с вставляемой точкой и добавялем ещё два фейсаочереди для рассмотрения. Если же точка лежит на ребре, два смежных с ребром фейса превращаем в два новых, добавляем ещё два, а так же превращаем реброЗатем, вы запустим алгоритмы Дейкстры на которое вставляется точка, в ребро, которое заканчивается в этой точке, и вставляем три новых. Итого у нас появилось несколько новых рёбер. Они все хорошие доступной части P(по [[#newedgeslemma|лемме 7]]G), плохими могут оказаться только рёбра, противолежащие вставленной точке. Флипаем рёбра, пока триангуляция не станет хорошейКаждый узел рассмотрел Дейкстрой представляет путь решения. ==== Вставка точкиЕсли точнее, лежащей снаружи триангуляции ====Представим, что вне триангуляции — бесконечные треугольники, основания которых — рёбра выпуклой оболочки триангуляции, а противолежащая ребру вершина — это бесконечно удалённая точка. Тогда понятно, что вставка точки, не лежащей то путь \sigma в триангуляции, сведётся к вставке точки внутрь триангуляции, если мы научимся обрабатывать бесконечные фейсы. Бесконечно удалённая точка имеет координаты <tex>(0,0,1,0)</tex> P(последняя координата — однороднаяG). Тогда проверка на то, по которому Дейкстра достигла этого узла является ли хорошим ребро, инцидентное бесконечно удалённой точке, упрощается:<tex>решением. Путь s-t может быть построен из \begin{vmatrix}a_x & a_y & a_x^2 + a_y^2 & 1 sigma за линейное время путем вычисления последовательности запасных ребер seq(\\b_x & b_y & b_y^2 + b_y^2 & 1 \\c_x & c_y & c_x^2 + c_y^2 & 1 \\0 & 0 & 1 & 0\end{vmatrix} = \begin{vmatrix}a_x & a_y & 1 \\b_x & b_y & 1 \\c_x & c_y & 1\end{vmatrix}</tex>sigma) и затем s-t пути из неё. Если Дейкстра находит k кратчайших путей, то есть достаточно проверить поворот трёх остальных точек образованного двумя бесконечными треугольниками четырёхугольникаK* завершается успешно. ПроверкаИначе, принадлежит ли точка бесконечному треугольнику, тоже проста: нужно, чтобы из точки было видно ребро, противолежащее бесконечно удалённой точке, в бесконечном треугольникеA* возобновляется для исследования большей части G. Это проверяется предикатом поворота. ==== Время работы ===={{Лемма|about=8|statement=При вставке точки будут флипаться только рёбраприводит к росту P(G), противолежащие вставленной точкена котором алгоритм Дейкстры затем будет возобновлен.|proof=[[Файл:Flip edges.png|400px|thumb|right|V — вставленная точкаМы будем повторять этот процесс до тех пор, ребро AC — плохое]]Доказательство по индукции. База. По [[#newedgeslemma|лемме 7]] изначально пока алгоритм Дейкстры не будут флипаться новые рёбра, инцидентные точке, то есть плохими могут оказаться только рёбра, противолежащие точкенайдет k кратчайших путей. ПереходАлгоритм 1 содержит псевдокод K*. Рассмотрим, что произойдёт Код с противолежащим точке <tex>V</tex> ребром <tex>AC</tex> после флипа8 по 25 строчку образует главный цикл K*. Цикл завершается, если оно плохоекогда очереди обоих алгоритмов А* и Дейкстры пусты. До вставки точки <tex>V</tex> для триангуляции выполнялся глобальный критерий Делоне, поэтому в окружности, описанной вокруг треугольника <tex>ACD</tex>8 строчки выполняет некоторые подготовительные вещи. После инициализации, А* запускает на 5 строчке пока вершина t не будет лежать никаких точек, кроме точки <tex>V</tex>. Можно построить окружностьвыбрана им для рассмотрения, касающуюся её изнутри в точке <tex>D</tex> и проходящую через точку <tex>V</tex>этом случае кратчайший путь s-t будет найден. В ней тоже Если t не окажется никаких точекдостигнута, так как она касается изнутрито алгоритм завершается без решения. ЗначитОтметим, для ребра <tex>VD</tex> выполняется критерий Делоне. Значит, после флипа ребро <tex>AC</tex> уже что он не будет флипатьсязавершится на бесконечных графах. Так как для рёбер <tex>AV</tex> и <tex>CV</tex> выполняется критерий ДелонеИначе, то плохими после флипа могут стать только рёбра <tex>AD</tex> и <tex>CD</tex> — то есть рёбраалгоритм добавляет специальную вершину R, противолежащие точке <tex>V</tex>.}}{{Лемма|about=9|statement=Средняя степень вершины после вставки её в триангуляцию Делоне равна <tex>Oкоторая назначена корнем P(1G)</tex>.|id=deglemma|proof=Предположим, что мы вставляем <tex>i+1</tex>-ую точку из последовательности из <tex>n</tex> точекв поисковую очередь алгоритма Дейкстры. Рассмотрим все перестановки из этих <tex>i+1</tex> точекЗатем, означающие порядок вставки этих точек. Всего таких перестановок <tex>(i+1)!</tex>K* входит в главный цикл. Тогда средняя степень последней вершины среди перестановок равна: <tex>E(\operatorname{deg}(v_{i+1}))=\frac {\sum_{p=perm(v_1, v_2K* поддерживает механизм планирования для контролирования, когда A* или Дейкстра будет возобновлены..., v_{i+1})} \operatorname{deg} (p[i+1])} {(i+1)!}</tex> Каждая Если очередь из <tex>i+1</tex> вершин побывает последней ровно <tex>i!</tex> разA* не пуста, поэтому: <tex>E(\operatorname{deg} (v_{i+1}))=\frac {\sum_{k=0}^{i} i! \operatorname{deg} (v_k)} {(i+1)!} = \frac {\sum_{k=0}^i \operatorname{deg}(v_k)} {i+1} = \frac {O(i+1)} {i+1} = O(1)</tex>}}{{Теорема|statement=При вставке точки в триангуляцию Делоне в среднем придётся сделать <tex>O(1)</tex> флипов.|id=flipnumberlemma|proof=Все флипнутые рёбра окажутся инцидентными вставленной точке (по лемме 8)что означает, а [[#deglemma|степень вершины — <tex>O(1)</tex> (по лемме 9)]]. Поэтому будет сделано <tex>O(1)</tex> флипов.}}Так как среднее число флипов — <tex>O(1)</tex>что А* ещё не завершил исследования всего графа G, то время вставки целиком зависит от времени локализации. === Удаление точки ======= Алгоритм ====При удалении точки получится {{Acronym|звёздный многоугольник, который можно затриангулировать за линию|Общеизвестный факт}}. При этом все рёбра, полученные в результате триангуляции звёздного многоугольника, могут оказаться плохими, поэтому необходимо пройтись по ним Дейкстра возобновляется тогда и пофлипатьтолько тогда, если нужно.==== Время работы ===={{Acronym|Средняя степень вершины в триангуляции — <tex>Oкогда g(1t)+ d </tex>|Общеизвестный факт}}, поэтому триангуляция звёздного многоугольника будет тоже за <tex>O= f(1u)</tex>. Новых рёбер получится <tex>O(1)</tex>, проверить их на локальный критерий Делоне и пофлипать тоже можно за <tex>O(1)</tex>Значение d является максимальным d-значением среди всех successor-ов головы поисковой очереди n алгоритма Дейкстры. Итого удаление точки работает за <tex>O(1)</tex>. == Constraints =={{Определение|definition='''Констрейнты''' — рёбра, которые нельзя флипатьВершина u является головой поисковой очереди A*.}}{{Утверждение|statement=Хорошая триангуляция с констрейнтом может быть хорошей с точностью до видимости через констрейнт.}}=== Вставка ===[[Файл:Constraint.png|400px|thumb|right|Красным выделен вставляемый констрейнт]]Смотрим на список рёбер, пересечённых ещё не вставленным констрейнтом, и флипаем их. Последнее флипнутое ребро и будет констрейнтом {{Acronym|(по понятным причинам)|Рёбра, пересечённые констрейнтом, после флипа будут начинаться в той же точкеНапомним, что и констрейнтd - функция расстояния, а заканчиваться в точке, в которой начинается ещё одно пересекающее ребро. Последнее же ребро будет начинаться и заканчиваться используемая в начале и конце констрейнта}}, после флипа пометим его как констрейнт. Затем флипаем всё, что могло стать плохим (кроме констрейнта), пока триангуляция вновь не станет хорошей.=== Удаление ===Аналогично: помечаем ребро как не-констрейнт и флипаем, пока не дойдём до хорошей триангуляцииалгоритме Дейкстры.