1632
правки
Изменения
м
[[ФайлПредположим, что мы вставляем <tex>i+1</tex>-ую точку из последовательности из <tex>n</tex> точек. Рассмотрим все перестановки из этих <tex>i+1</tex> точек, означающие порядок вставки этих точек. Всего таких перестановок <tex>(i+1)!</tex>. Тогда средняя степень последней вершины среди перестановок равна:drawing <tex>E(\operatorname{deg}(v_{i+1}))=\frac {\sum_{p=\operatorname{perm}(v_0, v_1, .png|400px|thumb|right|].., v_i)} \operatorname{deg} (p[i+1])} {(i+1)!}</tex> Каждая из <tex>i+1</tex> вершин побывает последней ровно <tex>i!</tex> раз, поэтому: <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}</tex> Пусть плоскость По лемме о рукопожатиях <tex>\alphasum_{k=0}^{i} \operatorname{deg}(v_k) = 2D</tex> пересекает сферу, где <tex>D</tex> - количество ребер. Следовательно: <tex>E(\operatorname{deg} (v_{i+1}))=\frac {2D} {i+1}</tex> Триангуляция Делоне на сфере является планарным графом на сфере, чья укладка эквивалентна укладке на плоскости. Из центра Значит, для неё справедлива формула Эйлера: <tex>OV-D+F=2</tex> опустим перпендикуляр , где <tex>OCV</tex> на плоскость - количество вершин, а <tex>F</tex> - количество граней. Так как каждая грань образована тремя рёбрами, и при этом при подсчёте каждое ребро учитывается дважды, имеем: <tex>3F=2D=>F=\alphafrac {2D} {3}</tex>.Подставив в формулу Эйлера, получим:
Соединим произвольную точку <tex>M</tex> линии пересения плоскости <tex>V-D+\alpha</tex> со сферой с точками <tex>O</tex> и <tex>C</tex>. Так как <tex>OC</tex> ⊥ <texfrac {2D} {3}=2=>\alpha</tex>, то <tex>OC</tex> ⊥ <texfrac {1} {3}D=V-2=>CMD=3(V-2)=3((i+1)-2)=3(i-1)</tex>.
Построим выпуклую оболочку наших точекИсходный многогранник был выпуклым.Если бы мы могли видеть грани, находящиеся вне нашего звездного многоугольника, то это бы значило, что от удаляемой вершины до вершины, противолежащей ребру звездного многоугольника и лежащей в этой грани можно было бы провести ребро. Которого изначально не было.И это ребро лежало бы вне нашего многогранника, что противоречило бы его выпуклости.}}Понятно, что мы постепенно перестаем видеть какие-то грани.Это происходит когда мы уходим ближе к центру, чем плоскость, соответствующая грани. {{Теорема|statement=Когда мы перестаем видеть грани, они исчезают в порядке, соответствующем выделению их как ушей в новой триангуляции.|id=deleteteorem|proof= # Расмотрим случай, когда у нас никакие четыре точки в звездном многоугольнике не лежат на одной окружности. Это значит, что все грани выпуклой оболочки будут треугольниками.Ухом является часть, которая по двум ребрам граничит с невидимыми гранями и по одному ребру может граничить с видимой.Посмотрим в каком порядке исчезают грани.Предположим нас есть кандидат на то, чтобы исчезнуть. Это какой-то выпуклый треугольник.Предположим, что у этого треугольника есть хотя бы два соседа, которые видны, но сам выпуклый многоугольник уже почти исчез (находится на одной плоскости с нашей точкой). Если мы видим две другие грани, то* рассмотрим центры отрезков.* рассмотрим <tex>\varepsilon</tex>-окресности центров отрезков. Если мы точку спустим к центру сферы еще немного, то этот треугольник виден не будет, но <tex>\varepsilon</tex>-окрестности будут видны две какие-то точки. Соединим их отрезком. Этот отрезок будет виден. Он не будет лежать на плоскости. Он не будет лежать под плоскостью. Тогла получается, что он лежит над плоскостью(ближе к краю сферы), значит, многогранник был невыпуклый.Получается, что грань ушла и у нее только один видимый сосед. Мы можем выделить грань как ухо.# Общий случай, когда четыре точки в звездном многоугольнике могут лежать на одной окружности рассматривается аналогично.
Все грани выпуклой оболочки окажутся внутри сферы. Поскольку, все точки лежат на сфереТеперь у нас возможна ситуация, когда перестает быть видимым не найдётся точек, которые будут лежать за гранями выпуклой оболочки, иначе выпуклую оболочку можно было бы расширить. Таким образом, все точки, будут принадлежать выпуклой оболочке.Так же ясно,что критерий Делоне будет выполняться, поскольку для каждой грани не будет точек, которые лежат выше нее. Поскольку никакие четыре точки не лежат на одной окружности в исходном наборе точекухо, а значитгрань, гранями выпуклой оболочки будут треугольничкиявляющаяся выпуклым многоугольником(по [[#poly|лемме 2]]).ЗначитВсе хорошо, триангуляция существует.А поскольку выпуклая оболочка единственна, можно сказать,что и триангуляция единственнапо [[#triagpoly|лемме 3]] мы можем триангулировать эту грань как угодно.
Если случилось так====Алгоритм удаления точки====# Уберем точку.# Сделаем приоритетную очередь, что у нас есть четыре или более точекв которой будем хранить пары отрезков, лежащих на одной окружностиобразующие ухо. Для этой очереди будем использовать предикат, то у построенной выпуклой оболочкисортирующий уши в порядке, возможно, будут грани, не являющиеся треугольникамив котором они пересекают луч по направлению от удаляемой точки к центру сферы. Понятно# На очередном шаге достаем ухо, что такие грани будут выпуклыми многоугольникамиотделяем его. Тогда каждую из них можно затриангулировать [[Триангуляция полигонов (ушная + монотонная)|методом отрезания "ушей"]]. Получившиеся треугольники будут лежать # Добавляем в одной плоскости и,следовательно, не будут нарушать критерий Делонеочередь получившиеся новые уши.В этом случае триангуляция может быть не единственна.===Время работы==Предикат=====Мы можем построить выпуклую оболочку за [[Файл:sphere_del.png|400px|thumb|right| <tex> \mathcalABC</tex> {{---}} грань, <tex> O}(n \log(n)) </tex>{{---}} центр сферы, где <tex>nP </tex> {{---}} количество точекудаляемая точка ]]При удалении точки, луч, исходящий из центра окружности в точку, пересекает плоскость очередной грани в некоторй точке <tex> T</tex>.Триангуляция выпуклого многоугольника требует времени Эту точку можно записать как <tex> \mathcal{T = O}(k) + kP </tex>, где <tex>kO </tex> {{---}} центр сферы, а <tex> p </tex> {{---}} число вершин с многоугольникеудаляемая точка. СледовательноЗпишем предикат при которм наша точка <tex>kP</tex> лежит на плоскости, проходящей через <tex>ABC</tex>:<tex>\begin{vmatrix} A & 1 \\ B & 1 \\ C & 1 \\ kP & 1 \end{vmatrix} = 0 </tex> Распишем и разложим по последней строке:<tex>\begin{vmatrix} A & 1 \\ B & 1 \\ C & 1 \\ kP & 1 \end{vmatrix} = \begin{vmatrix} a_x & a_y & a_z & 1 \\ b_x & b_y & b_z & 1 \\ c_x & c_y & c_z & 1 \\ kp_x & kp_y & kp_z & 1 \end{vmatrix} = k\begin{vmatrix} A & 1 \\ B & 1 \\ C & 1 \\ P & 0 \end{vmatrix} + \begin{vmatrix} A \\ B \\ C \end{vmatrix} = 0</tex> Тогда условие, по которому мы будем устанавливать порядок в худшем случае нам потребуется суммарно приоритетной очереди будет::: <tex>k = - \frac{\begin{vmatrix} A & 1 \\ B & 1 \\ C & 1 \\ P & 0 \end{vmatrix}}{\begin{vmatrix} A \\ B \\ C \end{vmatrix}}</tex> ====Время работы====Если наш звездный многоугольник состоит из <tex>k</tex> точек, то на один запрос приоритетной очереди будет уходить <tex> \mathcal{O}(n\log(k)) </tex> операции, чтоб перетриангулировать все грани, оказавшиеся многоугольниками после построения выпуклой оболочкиопераций.Таким образом, время работы всего алгоритма Значит общая ассимптотика будет <tex> \mathcal{O}n (k \log(nk)) </tex>.
rollbackEdits.php mass rollback
{{nohatewasted}}== Определение Определения ==
{{Определение
|definition=
'''Триангуляция''' — набор непересекающихся отрезков, соединениющий соединяющий заданный набор точек так, что добавление новых отрезков невозможно без пересечения уже имеющихся.
}}
{{Определение
|definition=
'''ОтрезокКритерий Делоне (частный случай для сферы):''' — кратчайшее расстояние от при построении плоскости через три точки до , которые образуют треугольник, все остальные точки лежат не выше этой плоскости.}} ==Существование триангуляции Делоне=={{Лемма|about=1|id=1|statement= Сечение сферы плоскостью есть окружность, а основание перпендикуляра, проведенного из центра шара к пересекаемой плоскости, есть центр окружности, полученной в сечении.|proof=[[Файл:drawing.png|400px|thumb|right|]]Пусть плоскость <tex>\alpha</tex> пересекает сферу. Из центра <tex>O</tex> опустим перпендикуляр <tex>OC</tex> на заданной поверхностиплоскость <tex>\alpha</tex>. Соединим произвольную точку <tex>M</tex> линии пересечения плоскости <tex>\alpha</tex> со сферой с точками <tex>O</tex> и <tex>C</tex>. Так как <tex>OC</tex> ⊥ <tex>\alpha</tex>, то <tex>OC</tex> ⊥ <tex>CM</tex>. Рассмотрим треугольник △<tex> OCM </tex> : <tex> CM^2 = OM^2 - OC^2</tex>. Т.к. <tex>OM</tex> и <tex>OC</tex> - величины постоянные, то и <tex>CM</tex> - величина постоянная. Таким образом все точки линии пересечения плоскости <tex>\alpha</tex> и сферы равноудалены от точки <tex>C</tex>, поэтому эта линия пересечения является окружностью с центром в точке <tex>C</tex> и радиусом <tex>r = CM</tex>.
}}
{{Теорема
|statement=
Триангуляция Делоне существует, причём для каждого набора точек, в котором никакие четыре точки не лежат на одной окружности, она единственна.
|proof=
Построим выпуклую оболочку наших точек.
Все грани выпуклой оболочки окажутся внутри сферы. Поскольку, все точки лежат на сфере, не найдётся точек, которые будут лежать за гранями выпуклой оболочки, иначе выпуклую оболочку можно было бы расширить. Таким образом, все точки, будут принадлежать выпуклой оболочке.
Так же ясно,что критерий Делоне будет выполняться, поскольку для каждой грани не будет точек, которые лежат выше нее.
Поскольку никакие четыре точки не лежат на одной окружности в исходном наборе точек, а значит, гранями выпуклой оболочки будут треугольнички.
Значит, триангуляция существует.
А поскольку выпуклая оболочка единственна, можно сказать, что и триангуляция единственна.
}}
{{Лемма
|about=2
|id=2
|statement= Гранями выпуклой оболочки будут выпуклые многоугольники
|proof=
По определению, множество является выпуклым, если для любых двух точек, отрезок, соединяющий эти точки, тоже входит во множество. И наша оболочка является выпуклой.
Предположим, что грань выпуклой оболочки не выпуклый многоугольник. Тогда найдутся две точки, такие, что отрезок не лежит в грани. Тогда получается, что и вся оболочка не является выпуклой.
}}
{{Лемма
|about=3
|id=trianpoly
|statement= Если гранью выпуклой оболочки оказался многоугольник, то любая триангуляция данного многоугольника - триангуляция Делоне.
|proof=
Рассмотрим наш многоугольник и плоскость, построенную через любые три точки.
Если существует точка выше нашей плоскости, то мы могли бы расширить нашу выпуклую оболочку, что означает некорректность построенной выпуклой оболочки. Противоречие.
Если существует точка ниже нашей плоскости, то "внутри" выпуклой оболочки содержится точка, что некорректно. Противоречие.
Отсюда, все точки лежат на плоскости, что в нашем случае эквивалентно тому, что они лежат на одной окружности, значит любая триангуляция нашего многоугольника не нарушит глобальный критерий Делоне(ни в одной окружности, построенной на появившихся в ходе триангуляции треугольников, не будет содержаться точек).
}}
Воспользовавшись фактом выше, приходим к очевидному решению как за <tex>O(K)</tex> (где <tex> K </tex>- количество вершин в многоугольнике) триангулировать все многограники: берем любую точку в многогранике и соединяем её с остальными.
Так как в конечной триангуляции мы имеем <tex>O(N)</tex> треугольников, а каждый шаг мы добавляем 1 треугольник, то суммарно для всех многоугольник мы совершим не более <tex>O(N)</tex> операций.
==Статический алгоритм==
===Алгоритм===
Дополним множество наших точек, точкой <tex>O</tex>, являющейся центром сферы. Данная точка нам понадобится, если все точки оказались в одной полусфере.(более быстрая проверка, на то какие треугольники надо исключить, чем подсчет предиката).
# Построим для данного множества выпуклую оболочку
# Удалим все треугольники, которые содеражат вершину <tex>O</tex> (это обязательно будут треугольники и они будут существовать только в том случае, если точки лежат в одной полусфере)
# Пройдемся по всем "выжившим" граням выпуклой оболочки и триангулируем их.
===Корректность===
Корректность следует из теорем выше.
===Время работы===
Мы можем построить выпуклую оболочку за <tex> \mathcal{O}(N \log(N)) </tex>, где <tex>N</tex> {{---}} количество точек.
Удалить треугольники мы можем за <tex>\mathcal{O}(N)</tex>.
Триангулиравать грани мы можем за <tex>\mathcal{O}(N)</tex> как было показано выше.
В результате получаем <tex> \mathcal{O}(N \log(N)) </tex>,
==Локальный критерий Делоне==
{{Определение
|definition=
'''СимплексЛокальный критерий Делоне:'''при построении плоскости через три точки, образующие треугольник, противолежащие сторонам треугольника вершины соседей лежат ниже этой плоскости.}} {{Утверждение|id=krit_dol1|statement=Пусть имеются два треугольника на сфере: <tex>ABC</tex> и <tex>ABD</tex> и точка <tex>E</tex>, находящаяся над плоскостью <tex>ABC</tex>. Точка <tex>D</tex> находится ниже плоскости <tex>ABC</tex>. Сечение построенной на ребре <tex>AB</tex> и точке <tex>O</tex> делит сферу на две полусферы. Если полусфера, не содержащяя треугольник <tex>ABC</tex>, содержит точки <tex>E</tex> и <tex>D</tex>, то точка <tex>E</tex> лежит надо плоскостью <tex>ABD</tex>.|proof=Факт очевиден.}}{{Утверждение|id=krit_dol1|statement=Глобальный и локальный критерии Делоне равносильны.|proof=[[Файл:dol1.png|400px|thumb|right|]]Из глобального в локальный очевидно. Из локального в глобальный: Пусть выполняется локальный критерий, то есть для каждого треугольника мы можем провести плоскость, что соседние вершины для треугольника будут лежать не выше нашей плоскости.Но нашелся треугольник <tex>ABC</tex>, что для него не выполняется глобальный критерий, т.е существует какая-то точка <tex>E</tex>, которая лежит выше плоскости <tex>ABC</tex>.В силу того, что локальный критерий выполняется, эта точка не принадлежит соседним треугольникам, в частности смежному треугольнику <tex>ABD</tex> по ребру <tex>AB</tex> За <tex>AB</tex> мы обозначили ребро, из которого видна точка <tex>E</tex>, т.е такое ребро, что если провести сечение через точки <tex>A</tex>, <tex>B</tex> и <tex>O</tex> (англцентр окружности), то точка <tex>E</tex> содержится в полусфере, не содержащей треугольник <tex>ABC</tex>. ''simplex'' Так как точка <tex>E</tex> лежит над плоскостью <tex>ABC</tex>, а точка <tex>D</tex> под плоскостью <tex>ABC</tex>, то точка <tex>E</tex> лежит над плоскостью <tex>ABD</tex>.(с учетом того, что они лежат в одной полусфере, ребро AB общее и отделяет треугольник <tex>ABC</tex> от полусферы) (по утверждению выше) — геометрическая фигура Посмотрим, существует ли у треугольника <tex>ABD</tex> смежный треугольник, содержащий вершину <tex>E</tex>:#Если он существует, то локальный критерий для треугольника <tex>ADE</tex> не выполняется. Противоречие.#Если он не существует, являющаяся nто точка <tex>E</tex> так же будет лежать "над" каким-мерным обобщением то смежным с <tex>ABD</tex> треугольником, так как для треугольника<tex>ABD</tex> будут выполняться те же условия, что и для <tex>ABC</tex>. Перейдем к такому треугольнику и повторим шаг. Заметим, что наш процесс есть локализация. Мы пустили луч (в ту сторону, где видим точку <tex>E</tex>) из исходного треугольника и идём вдоль него. В какой-то момент мы окажемся рядом с треугольником <tex>XYZ</tex>, для которого точка E выше плоскости, построенной на его трех точках, и в тоже время вершина E содержится в соседнем треугольнике, что нарушает локальный критерий. Противоречие. Значит глобальный критерий Делоне выполняется.
}}
==Критерии Делоне для ребер==
{{Определение
|definition=
'''ТриангуляцияГлобальный критерий Делоне для ребра:''' — разбиение геометрической фигуры на симплексычерез ребро можно провести плоскость так, что все точки будут лежать не выше этой плоскости.
}}
{{Определение
|definition=
'''Критерий Локальный критерий Делонедля ребра:''' через ребро можно провести плоскость так, что вершины, противолежащие этому ребру, будут лежать не выше этой плоскости}} {{Утверждение|id=krit_dol2|statement=Глобальный и локальный критерии Делоне для ребра равносильны.|proof=[[Файл:dol2.png|right]]Из глобального в локальный очевидно, докажем обратно.Предположим противное, то есть найдётся такая плоскость, что вершины треугольников при построении плоскости ребре <tex>AB</tex> лежат под ней, но существует какая-то вершина <tex>F</tex> над ней. Проведём окружность с центром в сфере через три точки<tex>AB</tex> и выберем треугольник лежащий в одной полусфере с точкой <tex>F</tex>, назовём его <tex>ABC</tex>. Для треугольника <tex>ABC</tex> не выполняется глобальный критерий Делоне, поэтому воспользуемся алгоритмом из утверждения "Глобальный и локальный критерии Делоне равносильны" и найдем треугольник для которого не будет выполняться локальный критерий Делоне <tex>\Rightarrow</tex> для одного из ребер найденного треугольника не выполняется локальный критерий Делоне. !!!Следовательно, глобальный критерий Делоне для ребра выполняется.}}{{Утверждение|id=krit_dol3|statement=Критерии Делоне для ребер и треугольников равносильны.|proof=[[Файл:dol3.png|400px|thumb|right|]]Из треугольника в ребра: если для каждого треугольника выполнен критерий, образующие то для каждого ребра можно рассматривать плоскость при любом треугольнике при ребре. Обратно: Рассмотрим треугольник<tex>ABC</tex>, для каждого из ребра можно провести плоскость, такую что все остальные точки лежат ниже этой будут лежать не выше её. Три плоскости образуют трехмерный угол, снаружи которого нет точек (снаружи == выше каждой плоскости при ребре). В пересечении угла и плоскости<tex>ABC</tex> образуется тетраэдр. Если в нем нет точек, значит точек нет и над плоскостью треугольника (точек снаружи тетраэдра нету), значит глобальный критерий выполняется. Проверим это. Пусть в нем есть точки, тогда эти точки оказались внутри треугольника, тогда это не триангуляция.
}}
Будем называть '''хорошими''' те рёбра, для которых выполняется локальный критерий Делоне.
{{Лемма
|about=4
|id=fliplemmasphere
|statement=
Из двух рёбер, которые можно провести для пары треугольников, как минимум одно хорошее.
|proof=
}}
==Динамический алгоритм==
{{Определение
|definition=
Рассмотрим пару смежных треугольников. Рёбра этих треугольников образуют четырёхугольник с проведённой в нём диагональю. Операция замены этой диагонали на другую называется '''flip'''Локальный критерий Делоне:('''флип''' при построении плоскости ).}}Из [[#fliplemmasphere|леммы 4]] следует, что если ребро плохое, то флип сделает его хорошим.[[Файл:file12345.png|400px|thumb|right|Красное ребро — до флипа, зеленое — после]]{{Лемма|about=5|statement=Флип плохого ребра уменьшает разность объёмов сферы и выпуклого многогранника, построенного на точках с заданными ребрами.|id=volumelemma|proof= Рассмотрим два таких смежных треугольника, что ребро между ними является плохим.Четыре точки, принадлежащие смежным треугольникам, образуют тетраэдр. Проведём через три точкикакой-нибудь из двух треугольников плоскость. Вершина, противолежащая основанию тетраэдра, образующие треугольникявляющегося этим треугольником, противолежащие сторонам треугольника вершины соседей лежат ниже лежит выше этой плоскости(так как для плохого ребра не выполняется локальный критерий Делоне), то есть тетраэдр не включается в объем фигуры. После флипа станет выполняться локальный критерий Делоне, то есть тело станет включать в себя тетраэдр. Поэтому после флипа плохого ребра объём тела увеличится на объём этого тетраэдра.}}{{Лемма|about=6|id=6|statement=Флипами можно достичь хорошей триангуляции за конечное время.|proof=Всего триангуляций заданного множества точек конечное число, и среди них есть триангуляция Делоне. Последовательность флипов плохих рёбер триангуляции образует такую последовательность триангуляций, что разность объёмов сферы и многогранника, постоенного по триангуляции убывает ([[#volumelemma|по лемме 5]]). Эта последовательность конечна (при этом последней в последовательности является триангуляция Делоне), значит, число флипов, требуемых для достижения триангуляции Делоне, тоже конечно.
}}
{{ОпределениеЛемма|definitionabout=7'''Глобальный критерий |id=newedgeslemma|statement=Если в триангуляцию Делоне для ребравставить точку в некоторый треугольник и соединить его вершины с этой точкой, то получившиеся рёбра будут хорошими.|proof=[[Файл:''' Lemma7.jpg|right||Точка <tex>P</tex> вставлена в треугольник]]Пусть мы вставляем точку <tex>P</tex>. Предположим, она была вставлена в треугольник <tex>ABC</tex> не на ребро. Рассмотрим любое из рёбер — пусть это будет ребро <tex>PC</tex>. Тогда проведем через ребро можно провести точки <tex>A</tex>, <tex>B</tex>, <tex>C</tex> плоскость <tex>\alpha</tex>, а также проведем касательную плоскость <tex>\beta</tex> к сфере через точку <tex>C</tex>. Начнем уменьшать между этими плоскостями угол, что вращая <tex>\alpha</tex> к <tex>\beta</tex> вокруг их линии пересечения. В какой-то момент <tex>\alpha</tex> пересечет точку <tex>P</tex>, а тогда мы предоставили плоскость, от которой все точки будут лежать ниже этой плоскоститриангуляции находятся по одну сторону, так как изначально выше <tex>\alpha</tex> была только точка <tex>P</tex>, а значит, ребро <tex>PC</tex> удовлетворяет глобальному критерию Делоне. Аналогично для ребер <tex>PA</tex> и <tex>PB</tex>. Случай, когда точка вставляется на ребро, рассматривается аналогично.
}}
{{ОпределениеУтверждение|definitionid=trianglepossession'''Локальный критерий Делоне для ребра:''' через ребро можно провести плоскость так|statement=Пусть даны точки <tex>P</tex>, <tex>A</tex>, <tex>B</tex>, <tex>C</tex> на сфере с центром <tex>O</tex>, тогда <tex>P</tex> принадлежит треугольнику <tex>ABC</tex>, тогда и только тогда, что вершиныкогда поворот <tex>P</tex> относительно плоскостей <tex>AOB</tex>, противолежащие этому ребру<tex>BOC</tex>, будут лежать ниже этой плоскости<tex>COA</tex> одинаковый.
}}
====Проверка местоположения точки относительно окружности описанной около треугольника====
[[Файл:1st pred dol ph.png|right]]
Рассмотрим <tex> \triangle ABC </tex> и некоторую точку <tex> D </tex>, все точки лежат на сфере. Задача состоит в том чтобы проверить, где лежит точка <tex> D </tex> относительно окружности описанной около <tex> \triangle ABC </tex>. Заметим, что 3 точки задают плоскость, которая пересекает сферу, образует окружность описанную около <tex> \triangle ABC </tex> и все точки на сфере, что лежат внутри окружности будут находится над плоскостью. Переформулируем задачу, мы будем искать положение точки <tex> D </tex> относительно плоскости <tex> \triangle ABС </tex>. Заметим, что если угол между нормалью <tex> \triangle ABC </tex> и вектором <tex> AD < 90 </tex>, то точка лежит над плоскостью, если <tex> = 90 </tex>, то на плоскости, а если <tex> > 90 </tex>, то снизу. Это означает, найдя скалярное произведение этих векторов мы определим положение точки относительно описанной окружности. Т к нам важен только знак скалярного произведения, то <tex> \vec{n}_{ABC} </tex> можно не нормировать.
<tex> \vec{n}_{ABC} = (B - A) \times (C - A) </tex>
<tex> k =\vec{n}_{ABC} \cdot (D - A) =Существования ((B - A),(C - A),(D - A)) = \begin{vmatrix} B - A \\ C - A \\ D - A \end{vmatrix} </tex><tex> = \begin{vmatrix} B & 1 \\ C & 1 \\ D & 1 \\ A & 1 \end{vmatrix} = - \begin{vmatrix} A & 1 \\ B & 1 \\ C & 1 \\ D & 1 \end{vmatrix} </tex> ===Вставка точки=== В самом начале для удобства реализации добавим к триангуляции Делонецентр сферы. Первую добавленную точку на сфере соединим с точкой <tex>O</tex>, вторую точку соединим с предыдущей точкой и центром сферы, третью - со всеми предыдущими. Получим выпуклое тело, далее точки вставляются либо на поверхность этого тела, либо за ее пределами. ==== Вставка точки, лежащей внутри триангуляции ====[[Файл:Add_into.jpg|left||Вставка внутрь треугольника]][[Файл:Add_on_edge.jpg|right||Вставка на ребро треугольника]]Пусть мы добавляем точку <tex>P'</tex>. Для начала локализуемся: поймём, в каком фейсе она лежит (или на каком ребре). Если точка лежит внутри фейса, добавляем три ребра, сам фейс превращаем в один из новых смежных с вставляемой точкой и добавялем ещё два фейса. Если же точка лежит на ребре, два смежных с ребром фейса превращаем в два новых, добавляем ещё два, а так же превращаем ребро, на которое вставляется точка, в ребро, которое заканчивается в этой точке, и вставляем три новых. Итого у нас появилось несколько новых рёбер. Они все хорошие (по [[#newedgeslemma| лемме 7]]), плохими могут оказаться только рёбра, противолежащие вставленной точке. Флипаем рёбра, пока триангуляция не станет хорошей. ====Вставка точки, лежащей снаружи триангуляции====[[Файл:Insert.jpg|right||Вставка в треугольник]] Пусть мы добавляем точку <tex>P''</tex>. Нам нужно научиться вставлять точку в треугольник, одной из вершин которого является центр сферы. На самом деле, это теперь получится сделать естественным образом. Так как для определения принадлежности точки треугольнику на поверхности сферы мы смотрим на предикат поворота относительно плоскости, проходящей через центр сферы и ребро, и вставляемой точки <tex>P''</tex>, то для проверки попадания в треугольник, содержащий центр сферы достаточно проверить, что точка <tex>O</tex> видна из точки <tex>P''</tex>, т.е. точка <tex>P''</tex> находится по определенную сторону от плоскости, проходящей через ребро и точку <tex>O</tex>, и противоположенная вершина для ребра является центром сферы. ====Время работы====
{{Лемма
|about=18|id=8|statement= Сечение сферы плоскостью При вставке точки будут флипаться только рёбра, противолежащие вставленной точке.|id=opposingedgeslemma|proof=Доказательство по индукции.[[Файл:Opposit_flip_named.jpg|right|| Флип противолежащего ребра]] База. По [[#newedgeslemma|лемме 7]] изначально не будут флипаться новые рёбра, инцидентные точке, то есть кругплохими могут оказаться только рёбра, противолежащие точке. Переход. Пусть мы вставили точку <tex>P</tex>. Рассмотрим, что произойдёт с противолежащим ей ребром <tex>AC</tex> после флипа, если оно плохое. До вставки точки <tex>P</tex> для триангуляции выполнялся глобальный критерий Делоне, поэтому плоскость <tex>\alpha</tex>, проходящая через точки <tex>A</tex>, <tex>C</tex> и <tex>D</tex> содержала все точки по одну сторону от себя, теперь же по другую сторону еще будет только точка <tex>P</tex>. Проведем плоскость <tex>\beta</tex> через точки <tex>P</tex> и <tex>D</tex> так, что линия пересечения <tex>\alpha</tex> и <tex>\beta</tex> лежала бы в одной плоскости с касательной на сфере через точку <tex>D</tex> к окружности, проходящей через точки <tex>A</tex>, <tex>C</tex> и <tex>D</tex>. Тогда уменьшая угол между этими плоскостями, вращая <tex>\alpha</tex> к <tex>\beta</tex> вокруг линии пересечения плоскостей, найдем момент, когда <tex>\alpha</tex> пересечет точку <tex>P</tex>, а основание перпендикуляра проведенного из центра шара к пересекаемой плоскости значит, в окружности, отсекаемой в этот момент плоскостью <tex>\alpha</tex> не будет никаких точек. Значит, ребро <tex>PD</tex> хорошее. Значит, после своего флипа ребро <tex>AC</tex> уже не будет флипаться. Так как для рёбер <tex>AP</tex> и <tex>CP</tex> выполняется критерий Делоне, то плохими после флипа могут стать только рёбра <tex>AD</tex> и <tex>CD</tex> — то есть центр кругарёбра, полученного противолежащие точке <tex>P</tex>.}}{{Лемма|about=О степени вершины|id=vertex_st|statement=Математическое ожидание степени вершины после её вставки в сечениитриангуляцию Делоне равно <tex>O(1)</tex>.|id=deglemma
|proof=
В прямоугольном треугольнике итоге <tex>OCM CM2 E(\operatorname{deg} (v_{i+1}))=\frac {2D} {i+1}= OM2 \frac {6(i- OC2</tex>. Т.к. <tex>OM</tex> и <tex>OC</tex> - величины постоянные, то и <tex>CM</tex> - величина постоянная. Таким образом все точки линии пересечения плоскости <tex>\alpha</tex> и сферы равноудалены от точки <tex>C</tex>, поэтому эта линия пересечения является окружностью с центром в точке <tex>C</tex> и радиусом <tex>r 1)} {i+1}= CMO(1)</tex>.
}}
{{Теорема
|statement=
При вставке точки в триангуляцию Делоне на сфере в среднем придётся сделать <tex>O(1)</tex> флипов.|id=flipnumberlemma|proof=Копирует случай на [[Триангуляция Делоне существует#flipnumberlemma|плоскости]].}} ===Удаление точки===В результате удаления у нас появляетя некоторый звездный многоугольник на сфере, который надо триангулировать.Из-за того, что у нас сфера, и задача триангуляции сведена к задаче построения выпуклой оболочки, то, следовательно, нам перестает быть важным критерий Делоне, причём для каждого набора точекнам просто нужно у звездного многоугольника на сфере как-то провести ребра так, чтобы было выпукло. Представим себе, что вместо того, чтобы удалять точку, мы просто опускаем ее во внутрь до тех пор, пока она не перестает быть видимой в котором никакие четыре точки не лежат построенном на одной окружноститриангуляции многоугольнике. Предположим, она единственначто мы находимся в удаляемой точке, движемся в центр сферы и смотрим только в направлении движения. {{Лемма|about=9|id=9|statement=Изначально нам будут видны грани, которые образуются внутри звездного многоугольника.|id=graniicansee
|proof=
Таким образом, мы будем перестраивать нашу выпуклую оболочку и, соответственно, триангуляцию.
}}
=Динамический алгоритм===Локализация в триангуляции===
Построим алгоритм на сфере по аналогии с плоскостью.
====Структура данных====
Локализационная структура состоит из нескольких уровней, где каждый уровень {{---}} триангуляция Делоне. На нижнем уровне содержатся все точки. Далее точка с вероятностью <tex> p </tex> попадает на следующий уровень. Если на последнем уровне находится одна точка, то дальше она уже не пойдет.
{{Лемма
|about=О количестве уровней
|id=10
|statement= Математическое ожидание уровней в локализационной структуре <tex> O(\log{n}) </tex>.
|proof= То же самое, что и для [[Триангуляция Делоне#levelslemma|плоскости]].
}}
===Принадлежность треугольнику===Пусть даны точки <tex>P</tex>, <tex>A</tex>, <tex>B</tex>, <tex>C</tex> на сфере с центром <tex>O</tex>, тогда <tex>P</tex> принадлежит треугольнику <tex>ABC</tex>, тогда и только тогда, когда поворот <tex>P</tex> относительно плоскостей <tex>AOB</tex>, <tex>BOC</tex>, <tex>COA</tex> одинаковый. =Алгоритм==Алгоритм===
Чтобы найти треугольник, которому принадлежит точка запроса(точка <tex>Q</tex>), сначала найдем ближайшую к ней точку триангуляции(точка <tex>P</tex>), а зачем вдоль луча <tex>PQ</tex> будем обходить треугольники, пока не локализуемся.
{{Лемма
|about=110|id=111
|statement=Алгоритм найдет ближайшую точку
|proof=Допустим, что это не так. Это значит, что в внутри окружности с центром в точке <tex>Q</tex>, на которой лежит точка <tex>P</tex>, есть какие-то другие точки. То есть другими словами существует плоскость <tex>\alpha</tex> проходящая через точку <tex>P</tex>, выше которой находятся точка <tex>Q</tex>(так как она центр) и какие-то точки триангуляции.
{{Лемма
|about=211|id=212
|statement=Среднее число точек, лежащих внутри окружности с центром в точке <tex>Q</tex> и проходящей через точку <tex>V_{i + 1}</tex> равно <tex>O(1)</tex>.
|proof=Рассмотрим точки триангуляции <tex>\{A_i\}</tex>. Для каждой точки <tex> A_i</tex> проведем окружность с центром в ней, проходящую через ближайшую к ней точку. Посчитаем во сколько окружностей в среднем попадет точка какая-то точка <tex>U</tex>.
Если на <tex>j</tex>-ой позиции находится черная точка, то точки с индексом <tex>j + 1</tex> и далее не будут содержать в окружности точку <tex>U</tex>(потому что <tex>j</tex> была ближайшей на предыдущем уровне из этой части пространства). Тогда если <tex> X </tex> {{---}} количество окружностей, которым принадлежит точка <tex>U</tex>, то так как точка проходит на следующий уровень с вероятностью <tex>p</tex>:
<tex dpi = 150>E(X) \leqslant \sum\limits_sum_{i = 1\dots}^{\infty}{i \cdot p(1 - p) ^ i} = </tex><tex dpi = 150>\sum\limits_sum_{i = 1\dots}^{\infty}{\sum\limits_sum_{j = i\dots}^{\infty}{p (1 - p) ^ j}} = </tex><tex dpi = 150>p\sum\limits_sum_{i = 1\dots}^{\infty}{(1-p)^i \cdot (\sum\limits_sum_{j = 0\dots}^{\infty}{(1 - p) ^ j})} = \sum\limits_sum_{i = 1\dots}^{\infty}{(1-p)^i} = \fracdfrac{1-p}{p} = O(1)</tex>
Получается, что каждая точка принадлежит <tex>O(1)</tex>, следовательно внутри каждой окружности содержит <tex>O(1)</tex> точек.
}}
{{Лемма
|about=312|id=313|statement=Средняя степень точек на <tex>i</tex> уровне внутри окружности с центром в точке <tex>Q</tex> и проходящей через точку <tex>P_{i + 1}</tex>(ближайшая точка на <tex>i + 1</tex> уровне)равна <tex>O(1)</tex>
|proof=Пусть есть функция <tex>circle(q, p, i)</tex>, возвращающая <tex>1</tex>, если точка <tex>p</tex> принадлежит окружности с центром в точке <tex>q</tex>, проходящую через ближайшую к <tex>q</tex> на <tex>i</tex> уровне точку, а иначе <tex>0</tex>.
{{Лемма
|aboutid=15|statement=4Степень ближайшей вершины <tex>O(1)</tex>|proof=Доказательство копирует случай на [[Триангуляция Делоне#nearestdegreelemma|плоскости]].}} {{Лемма|id=416
|statement=Один уровень в среднем обрабатывается за <tex>O(1)</tex>
|proof=По [[#2|лемме 211]] алгоритм пройдет в среднем <tex>O(1)</tex> вершин, степень которых так же равна по [[#3|лемме 312]] <tex>O(1)</tex>, следовательно один уровень будет обработан за <tex>O(1)</tex>.}} {{Лемма|id=17|statement=На втором этапе алгоритма луч в среднем пересечет <tex>O(1)</tex> ребер.|proof=Рассмотрим окружность с центром в точке <tex>Q</tex>, проходящую через ближайшую для неё точку триангуляции <tex>P_{i + 1}</tex>. Количество таких ребер, хотя бы одна граница которых принадлежит окружности не превосходит суммы степеней вершин внутри окружности, следовательно их <tex>O(1)</tex>.Осталось посчитать ребра, границы которых не лежат внутри окружности. При вставке точки <tex>Q</tex> в триангуляцию для таких ребер испортится критерий Делоне, так как внутри любой окружности построенной на этом ребре будет либо точка <tex>Q</tex>, либо точка <tex>P_{i + 1}</tex>. Значит, что эти ребра надо будет флипнуть, а так как при вставке в среднем флипается <tex>O(1)</tex> ребер, то луч пересечет <tex>O(1)</tex> ребер.
}}
|about=Следствие
|statement=Локализация в среднем работает за <tex>O(\log{n})</tex>
|proof=
}}
{{Лемма
|id=18
|statement=Точка на сфере может быть ближайшей для не более <tex>6</tex> точек.
|proof=Пусть это не так. Тогда некоторая точка <tex>P</tex> является ближайшей для <tex>7</tex> точек: <tex>A_1 \dots A_7</tex>. Проведем отрезки <tex>P A_i</tex>. Сумма углов между этими отрезками(дугами) равна <tex>2\pi</tex>
Рассмотрим треугольник <tex>A_i P A_{i + 1}</tex>, где угол <tex>A_i P A_{i + 1}</tex> минимальный. Он строго меньше <tex>\dfrac{\pi}{3}</tex> (иначе сумма углов была бы больше <tex>2\pi</tex>).
[[https://lurklurk.com/Британские_учёные |Британкие ученые доказали]}, что сумма углов в сферическом треугольнике строго больше <tex>\pi</tex>(школьный факт).
Однако по сферической теореме синусов напротив максимальной стороны лежит максимальный угол. Значит в таком треугольнике сумма углов меньше <tex>\pi</tex>. Противоречие.
}}
====Движение вдоль луча====
Когда нам надо пройти по триангуляции вдоль какого-то луча <tex>PQ</tex>, то ,оказавшись в каком-то треугольнике, надо проверить, что точка <tex>Q</tex> принадележит этому треугольнику. Если принадлежит, то мы останавливаем свой обход, иначе находим какую сторону пересекал луч и переходим в смежный этой стороне треугольник.
{{Теорема
|statement=Луч <tex>PQ</tex> пересекает отрезок <tex>AB</tex> тогда и только тогда, когда повороты точек <tex>A</tex> и <tex>B</tex> относительно <tex>PQ</tex> различены, а повороты <tex>B</tex> и <tex>Q</tex> относительно <tex>AP</tex> совпадают.
|proof='''Необходимость'''
<tex>AB</tex> пересекает <tex>PQ</tex>. Очевидно, что в этом случае повороты точек <tex>A</tex> и <tex>B</tex> относительно <tex>PQ</tex> различены. Рассмотрим повороты <tex>B</tex> и <tex>Q</tex> относительно <tex>AP</tex>. Если они различны, тогда луч <tex>PQ</tex> и отрезок <tex>AB</tex> лежат в разных полусферах, но они пересекаются, значит такого быть не может и повороты должны совпадать.
'''Достаточность'''
Предикат выполняется. Значит отрезок <tex>AB</tex> пересекает прямую <tex>PQ</tex>. Луч <tex>PQ</tex> в свою очередь есть половина прямой <tex>PQ</tex>. Из того, что повороты <tex>B</tex> и <tex>Q</tex> относительно <tex>AP</tex> совпадают, следует, что отрезок <tex>AB</tex> находится в одной полусфере с лучем <tex>PQ</tex>, значит они пересекаются.
}}
