Изменения

[[Файл:Kd-tree{{nohate}}== Определение =={{Определение|definition='''Подразбиение Делоне множества точек''' — такое разбиение выпуклой оболочки множества точек на множество выпуклых фигур, что в окружности, описанной вокруг любой из фигур, не находится никаких точек из множества.}}{{Определение|definition='''Триангуляция Делоне множества точек''' — триангуляция, являющаяся подразбиением Делоне.}} == Существование триангуляции Делоне =={{Лемма|about=1|statement=Окружность, спроецированная на параболоид, находится в одной плоскости. Все точки, лежащие внутри окружности, будут лежать под этой плоскостью. Точки, лежащие вне окружности, будут лежать над плоскостью.png }}{{Теорема| 400px statement=Подразбиение Делоне существует, причём для каждого набора точек оно единственно.| right]]proof=Спроецируем все точки на параболоид и построим выпуклую оболочку. Все грани выпуклой оболочки окажутся внутри параболоида из-за его выпуклости. При этом точки лежат на параболоиде. Поэтому не найдётся точек, которые будут лежать за гранями выпуклой оболочки. То есть все точки, спроецированные на параболоид, будут принадлежать выпуклой оболочке. По лемме 1 очевидно, что внутри окружностей, описанных вокруг проекций граней выпуклой оболочки, не будет лежать никаких точек. Значит, проекции граней — фигуры подразбиения Делоне. Значит, такое подразбиение существует.  Из единственности выпуклой оболочки следует, что такое подразбиение единственно.}}

== Критерий Делоне для рёбер =={{Определение|definition='''K-d деревоКритерий Делоне для ребра''' (short for k-dimensional tree) : на ребре можно построить такую окружность, что внутри неё не будет лежать никаких точек.}}{{---}} статическая структура данных для хранения точек в <tex>k</tex>-мерном пространстве. Позволяет отвечать Лемма|about=2|statement=Триангуляции Делоне принадлежат те и только те рёбра (с поправкой на точки, лежащие на запросодной окружности), какие точки лежат в данном прямоугольникекоторые удовлетворяют критерию Делоне.Строится это дерево следующим образом|proof=[[Файл: разобьём все точки вертикальной прямой так, чтобы слева (нестрого) и справа (строго) от неё было примерно поровну точек (для этого посчитаем медиану первых координат)Good edges. Получим подмножества для левого png|400px|thumb|right|Для рёбер AB и правого ребёнка. Далее построим CD выполняется критерий Делоне, на них построены окружности]]То, что для этих подмножеств деревьярёбер, но разбивать будем уже не вертикальнойпринадлежащих триангуляции Делоне, а горизонтальной прямой (выполняется критерий Делоне для этого посчитаем медиану вторых координат). И так далее рёбер, очевидно (будем считатьвокруг каждого ребра можно описать окружность, что <tex>k = 2</tex> (случай бОльших размерностей обрабатывается аналогично)проходящую через противолежащую ему точку в смежном треугольнике, поэтому на следующем уровне вновь будем разбивать вертикальными прямымипричём в окружности не будет никаких точек по критерию Делоне).

''Замечание: проблемы могут возникнутьДокажем, что если много точек имеют одинаковую координату, тогда разбить примерно поровну не получится (почти все точки будут лежать на медиане и попадут в левую часть). Лучший способ борьбы с этим {{---}} не вспоминать о данной проблеме совсем. Но вообще с этим борются, используя composite numbersдля ребра выполняется критерий Делоне, то есть сравнивая ещё и по другой (другим) координатеоно принадлежит триангуляции Делоне.''

Реализовывать построение можно рекурсивно с помощью функции Предположим, что это ребро (назовём его <tex>BuildKdTree(P, Depth)AB</tex>, принимающей множество точек и глубину) не принадлежит триангуляции Делоне. В зависимости от остатка при делении на размерность (при Тогда существует пересекающее его ребро <tex> k = 2 CD</tex> от чётности размерности) сплитим множество на два подмножества и делаем рекурсивные вызовы. Для лучшего понимания приведём псевдокод:<code> BuildKdTree(P, Depth) //Input. A set of points P and the current depth Depthпринадлежащее триангуляции. //Output. The root of a kd-tree storing P. if P contains only one point return a leaf storing this point else if depth is even Split P into two subsets Рассмотрим четырёхугольник <tex>P_1ACBD</tex> and . Точки <tex>P_2C</tex> with a vertical line и <tex>lD</tex> through the median x-coordinate of the points in P else Split P into two subsets лежат вне окружности, построенной на <tex>P_1AB</tex> and как на хорде, поэтому сумма углов <tex>P_2C</tex> with a horizontal line и <tex>lD</tex> through the median y-coordinate of the points in Pменьше 180°. <tex>V_{left}</tex> <- BuildKdTree(<tex>P_1</tex>Аналогичным образом доказывается, Depth + 1) что сумма углов <tex>V_{right}A</tex> <- BuildKdTree(и <tex>P_2B</tex>тоже меньше 180°. Значит, Depth + 1) Create a node v storing сумма углов четырёхугольника <tex>lACBD</tex>меньше 360°, make <tex>V_{left}</tex> the left child of vчто невозможно. Противоречие. Значит, and make ребро <tex>V_{right}AB</tex> the right child of vпринадлежит триангуляции Делоне. return v </code>}}

|about=3О времени построения|id=fliplemma

Построение выполняется за <tex>O(n \log n)</tex>Из двух рёбер, которые можно провести для пары треугольников, как минимум одно хорошее.

Время построения обозначим [[Файл:Bad edges.png|400px|thumb|right|Рёбра AB и BC плохие]]Предположим, что это не так, то есть оба ребра (назовём их <tex>T(nAB</tex> и <tex>CD</tex>)плохие. Рассмотрим четырёхугольник <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|400px|thumb|right|Все рёбра треугольника хорошие, но описанная окружность содержит точки]]Предположим, что это не так, то есть все рёбра хорошие, но существуют треугольники, описанная окружность которых содержат какие-либо точки триангуляции. Возьмём какую-либо конфликтную точку <tex>E</tex>. Рассмотрим такой треугольник <tex>ABC</tex> из тех, в описанную окружность которых попадает <tex>E</tex>, что угол <tex>BEC</tex> максимален, если <tex>BC</tex> — ближайшая к точке <tex>E</tex> сторона. Поиск медианы можно сделать за линейное времяПусть треугольник <tex>BDC</tex> — смежный с <tex>ABC</tex>. Докажем, поэтому достаточно очевидночто точка <tex>E</tex> лежит в окружности, описанной вокруг <tex>BDC</tex>. Предположим, чтоэто не так. Посмотрим на окружность, описанную вокруг треугольника <tex>ABC</tex>:<tex>\angle BAC + \angle BEC > 180^\circ</tex> и <tex>\angle BAC + \angle BDC < 180^\circ</tex>. Если точка <tex>E</tex> не лежит в окружности, описанной вокруг треугольника <tex>BDC</tex>, то <tex>\angle BEC < \angle BDC</tex>, что противоречит предыдущим двум неравенствам.

Очевидно, что угол <tex>T(n) = O(1)BED</tex> if больше, чем угол <tex>n = 1BEC</tex>.При этом точка <tex>E</tex> лежит в окружности, описанной вокруг <tex>BDC</tex>. Значит, при выборе треугольника нужно было взять не <tex>ABC</tex>, а <tex>BDC</tex>. Противоречие.}}

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

Решением этого является <tex>TПроведём через какой-нибудь из двух треугольников плоскость. Вершина, противолежащая основанию тетраэдра, являющегося этим треугольником, лежит ниже этой плоскости (nтак как не выполняется локальный критерий Делоне) = O(n \log n)</tex>, то есть тетраэдр лежит ниже тела, образующегося при проекции всей триангуляции на параболоид.

Также стоит отметитьПосле флипа станет выполняться локальный критерий Делоне, что то есть тело станет включать в себя тетраэдр. Поэтому после флипа плохого ребра объём тела увеличится на объём этого тетраэдра.}}{{Лемма|about=6|statement=Флипами можно и не искать медиану достичь хорошей триангуляции за линейное конечное время.|proof=Всего триангуляций заданного множества точек конечное число, а просто посортить все точки в самом начале и дальше использовать этосреди них есть триангуляция Делоне. Последовательность флипов плохих рёбер триангуляции образует такую последовательность триангуляций, что разность объёмов параболоида и спроецированной на него триангуляции убывает ([[#volumelemma|по лемме 5]]). В реализации попрощеЭта последовательность конечна (при этом последней в последовательности является триангуляция Делоне), значит, число флипов, требуемых для достижения триангуляции Делоне, асимптотика та жетоже конечно.

|about=О занимаемой памяти7

K-d дерево требует <tex>O(n)</tex> памятиЕсли в триангуляцию Делоне вставить точку в некоторый треугольник и соединить его вершины с этой точкой, то получившиеся рёбра будут хорошими.|id=newedgeslemma

Высота дерева[[Файл:Good edge.png|400px|thumb|right|Точка V вставлена в треугольник ABC]]Предположим, очевидно, логарифмическаяточка была вставлена не на ребро. Рассмотрим любое из рёбер — пусть это будет ребро <tex>VC</tex>. Проведём окружность, а листьев всего описывающую треугольник <tex>O(n)ABC</tex>. Поэтому По критерию Делоне в ней не будет никаких точек триангуляции. На ребре <tex>O(n)VC</tex> вершинможно построить окружность, изнутри касающуюся окружности, каждая занимает описанной вокруг треугольника. В ней тоже нет никаких точек. Значит, для <tex>O(1)VC</tex> памятивыполняется критерий Делоне для рёбер, значит, ребро должно принадлежать триангуляции с добавленной точкой <tex>V</tex>, значит, оно хорошее. Случай, когда точка вставляется на ребро, рассматривается аналогично.

By the wayДля начала локализуемся: поймём, если считать <tex>k</tex> константой, то и для случая большей размерности эти оценки будут такими же в каком фейсе лежит точка (доказывается аналогичноили на каком ребре).

== Запрос ==Пусть нам поступил какой-то прямоугольник <tex>R</tex>. Нужно вернуть все точкиЕсли точка лежит внутри фейса, которые в нём лежат. Будем это делать рекурсивнодобавляем три ребра, получая на вход корень дерева и сам прямоугольник <tex>R</tex>. Обозначим область, соответствующую вершине <tex>v</tex>, как <tex>region(v)</tex>. Она будет прямоугольником, одна или более границ которого могут быть на бесконечности. <tex>region(v)</tex> можно явно хранить фейс превращаем в узлах, записав при построении, или же считать при рекурсивном спуске. Если корень дерева является листом, то просто проверяем одну точку и при необходимости репортим её. Если нет, то смотрим пересекают ли регионы детей прямоугольник <tex>R</tex>. Если да, то запускаемся рекурсивно от такого ребёнка. При этом, если регион полностью содержится в <tex>R</tex>, то можно репортить сразу все точки один из него. Тем самым мы, очевидно, вернём все нужные точки новых смежных с вставляемой точкой и только ихдобавялем ещё два фейса. Чтобы стало совсем понятно, приведём псевдокод:

<code> SearchKdTree(vЕсли же точка лежит на ребре, R) //Input. The root of (a subtree of) a kd-treeдва смежных с ребром фейса превращаем в два новых, добавляем ещё два, а так же превращаем ребро, на которое вставляется точка, в ребро, and a range R. //Output. All points at leaves below v that lie in the range. if v is a leaf Report the point stored at v if it lies in R. else if region(v.left) is fully contained in R ReportSubtree(v.left) else if region(v.left) intersects R SearchKdTree(v.leftкоторое заканчивается в этой точке, R) if region(v.right) is fully contained in R ReportSubtree(v.right) else if region(v.right) intersects R SearchKdTree(vи вставляем три новых.right, R) </code>

Здесь Итого у нас появилось несколько новых рёбер. Они все хорошие (по [[#newedgeslemma|лемме 7]]), плохими могут оказаться только рёбра, противолежащие вставленной точке. Флипаем рёбра, пока триангуляция не станет хорошей. ==== Вставка точки, лежащей снаружи триангуляции ====Представим, что вне триангуляции — бесконечные треугольники, основания которых — рёбра выпуклой оболочки триангуляции, а противолежащая ребру вершина — это бесконечно удалённая точка. Тогда понятно, что вставка точки, не лежащей в триангуляции, сведётся к вставке точки внутрь триангуляции, если мы научимся обрабатывать бесконечные фейсы. Бесконечно удалённая точка имеет координаты <tex>(0,0,1,0)</tex>ReportSubtree(последняя координата — однородная). Тогда проверка на то, является ли хорошим ребро, инцидентное бесконечно удалённой точке, упрощается:<tex>\begin{vmatrix}a_x & a_y & a_x^2 + a_y^2 & 1 \\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> репортит все , то есть достаточно проверить поворот трёх остальных точек образованного двумя бесконечными треугольниками четырёхугольника. Проверка, принадлежит ли точка бесконечному треугольнику, тоже проста: нужно, чтобы из точки было видно ребро, противолежащее бесконечно удалённой точке, в поддеревебесконечном треугольнике. Это проверяется предикатом поворота. ==== Время работы ===={{Лемма|about=8|statement=При вставке точки будут флипаться только рёбра, противолежащие вставленной точке.|proof=[[Файл:Flip edges.png|400px|thumb|right|V — вставленная точка, ребро AC — плохое]]Доказательство по индукции.

By the wayБаза. По [[#newedgeslemma|лемме 7]] изначально не будут флипаться новые рёбра, точно так же можно перечислять точки в любом множествеинцидентные точке, ведь нигде не используетсято есть плохими могут оказаться только рёбра, что <tex>R</tex> {{---}} прямоугольникпротиволежащие точке.

Переход. Рассмотрим, что произойдёт с противолежащим точке <tex>V</tex> ребром <tex>AC</tex> после флипа, если оно плохое. До вставки точки <tex>V</tex> для триангуляции выполнялся глобальный критерий Делоне, поэтому в окружности, описанной вокруг треугольника <tex>ACD</tex>, не будет лежать никаких точек, кроме точки <tex>V</tex>. Можно построить окружность, касающуюся её изнутри в точке <tex>D</tex> и проходящую через точку <tex>V</tex>. В ней тоже не окажется никаких точек, так как она касается изнутри. Значит, для ребра <tex>VD</tex> выполняется критерий Делоне. Значит, после флипа ребро <tex>AC</tex> уже не будет флипаться. Так как для рёбер <tex>AV</tex> и <tex>CV</tex> выполняется критерий Делоне, то плохими после флипа могут стать только рёбра <tex>AD</tex> и <tex>CD</tex> — то есть рёбра, противолежащие точке <tex>V</tex>.}}{{ТеоремаЛемма|about=О времени на запрос9

Перечисление точек Средняя степень вершины после вставки её в прямоугольнике выполняется за триангуляцию Делоне равна <tex>O(\sqrt n + ans1)</tex>, где <tex>ans</tex> {{---}} размер ответа.|id=deglemma

Сперва заметимПредположим, что все мы вставляем <tex>ReportSubtreei+1</tex> суммарно выполняются за -ую точку из последовательности из <tex>O(ans)n</tex>точек. Поэтому достаточно доказать оценку для числа рекурсивных вызовов. А рекурсивные вызовы выполняются только для тех вершин, регионы которых пересекают Рассмотрим все перестановки из этих <tex>Ri+1</tex>точек, но не содержатся в нёмозначающие порядок вставки этих точек. Такие регионы обязательно пересекают хотя бы одну Всего таких перестановок <tex>(axis-paralleli+1) сторону заданного прямоугольника. Оценим количество регионов, которые могут пересекаться произвольной вертикальной прямой. Для горизонтальной прямой это будет аналогично!</tex>. Тогда средняя степень последней вершины среди перестановок равна:

Обозначим максимально возможное количество регионов, пересекаемых какой-либо вертикальной прямой, в дереве для <tex>n</tex> точекE(\operatorname{deg}(v_{i+1}))=\frac {\sum_{p=perm(v_1, у которого первое разбиение делается вертикальной прямойv_2, как <tex>Q(n)</tex>. Рассмотрим произвольную вертикальную прямую <tex>l</tex>. Она будет пересекать регион корня и какого-то одного из его детей ., v_{i+1})} \operatorname{deg} (например, левогоp[i+1]). При этом ни один из регионов в другом } {(правомi+1) поддереве пересекать она не может. Левая половина разбита ещё на 2 части горизонтальной прямой, в каждой из них примерно <tex>n / 4!}</tex> вершин, и они хранятся в поддереве, у которого первое разбиение делается вертикальной прямой. Это даёт нам следующее соотношение:

Каждая из <tex>Q(n) = O(i+1)</tex> if вершин побывает последней ровно <tex>n = 1i!</tex>.раз, поэтому:

<tex>QE(n\operatorname{deg} (v_{i+1}))=\frac {\sum_{k=0}^{i} i! \operatorname{deg} (v_k) } {(i+1)!} = 2 \frac {\sum_{k=0}^i \operatorname{deg}(v_k)} {i+ 2 1} = \cdot Qfrac {O(i+1)} {i+1} = O(1)</tex>}}{{Теорема|statement=При вставке точки в триангуляцию Делоне в среднем придётся сделать <tex>O(1)</tex> флипов.|id=flipnumberlemma|proof=Все флипнутые рёбра окажутся инцидентными вставленной точке (по лемме 8), а [[#deglemma|степень вершины — <tex>O(1)</tex> (n по лемме 9)]]. Поэтому будет сделано <tex>O(1)</ 4tex> флипов.}}Так как среднее число флипов — <tex>O(1)</tex>, otherwiseто время вставки целиком зависит от времени локализации. === Удаление точки ======= Алгоритм ====При удалении точки получится {{Acronym|звёздный многоугольник, который можно затриангулировать за линию|Общеизвестный факт}}. При этом все рёбра, полученные в результате триангуляции звёздного многоугольника, могут оказаться плохими, поэтому необходимо пройтись по ним и пофлипать, если нужно.==== Время работы ===={{Acronym|Средняя степень вершины в триангуляции — <tex>O(1)</tex>|Общеизвестный факт}}, поэтому триангуляция звёздного многоугольника будет тоже за <tex>O(1)</tex>. Новых рёбер получится <tex>O(1)</tex>, проверить их на локальный критерий Делоне и пофлипать тоже можно за <tex>O(1)</tex>. Итого удаление точки работает за <tex>O(1)</tex>.

Нетрудно заметить== Constraints =={{Определение|definition='''Констрейнты''' — рёбра, что <tex>Q(n) которые нельзя флипать.}}{{Утверждение|statement= O(\sqrt n)</tex> является решением. Принимая во внимание всё, что писалось выше, получаем требуемоеХорошая триангуляция с констрейнтом может быть хорошей с точностью до видимости через констрейнт.

By the way=== Вставка ===[[Файл:Constraint.png|400px|thumb|right|Красным выделен вставляемый констрейнт]]Смотрим на список рёбер, пересечённых ещё не вставленным констрейнтом, и флипаем их. Последнее флипнутое ребро и будет констрейнтом {{Acronym|(по понятным причинам)|Рёбра, пересечённые констрейнтом, после флипа будут начинаться в той же точке, что и констрейнт, а заканчиваться в общем случае время на запрос <tex>O(n^{1 - 1/kточке, в которой начинается ещё одно пересекающее ребро. Последнее же ребро будет начинаться и заканчиваться в начале и конце констрейнта}} + ans)</tex> из соотношения <tex>Q, после флипа пометим его как констрейнт. Затем флипаем всё, что могло стать плохим (nкроме констрейнта) , пока триангуляция вновь не станет хорошей.= k + 2^{k == Удаление ===Аналогично: помечаем ребро как не- 1} \cdot Q(n / 2^k)</tex>констрейнт и флипаем, пока не дойдём до хорошей триангуляции.