Изменения

{{nohatewasted}}== Определение Определения ==

'''Триангуляция''' — набор непересекающихся отрезков, соединениющий соединяющий заданный набор точек так, что добавление новых отрезков невозможно без пересечения уже имеющихся.}}{{Определение|definition='''Отрезок''' — кратчайшее расстояние от точки до точки на заданной поверхности.}}{{Определение|definition='''Симплекс'''(англ. ''simplex'') — геометрическая фигура, являющаяся n-мерным обобщением треугольника.}}{{Определение|definition='''Триангуляция''' — разбиение геометрической фигуры на симплексы.

'''Критерий Делоне(частный случай для сферы):''' при построении плоскости через три точки, образующие которые образуют треугольник, все остальные точки лежат ниже не выше этой плоскости.

|id=1|statement= Сечение сферы плоскостью есть кругокружность, а основание перпендикуляра , проведенного из центра шара к пересекаемой плоскости , есть центр кругаокружности, полученного полученной в сечении.

Соединим произвольную точку <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 CM2 </tex> : <tex> CM^2 = OM2 OM^2 - OC2OC^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= Если гранью выпуклой оболочки оказался многоугольник, то его можно треангулировать любым способом, критерий любая триангуляция данного многоугольника - триангуляция Делоне всеравно будет выполняться.

Грань могла оказаться многоугольником только в том случаеРассмотрим наш многоугольник и плоскость, если все построенную через любые три точки. Если существует точка выше нашей плоскости, образующие еёто мы могли бы расширить нашу выпуклую оболочку, лежат на одной окружностичто означает некорректность построенной выпуклой оболочки. Противоречие. В противном случае, через точкиЕсли существует точка ниже нашей плоскости, лежащие на окружности(таких как минимум три) можно было бы провести плоскость и все остальные точки этой грани лежали бы выше или ниже и противоречили бы тому фактуто "внутри" выпуклой оболочки содержится точка, что выпуклая оболочка строится корректнонекорректно. Противоречие.

Тогда получаетсяОтсюда, что все наши точки лежат на плоскости, что в нашем случае эквивалентно тому, что они лежат на одной плоскостиокружности, и как бы мы значит любая триангуляция нашего многоугольника не разбивали грань нарушит глобальный критерий Делоне(ни в одной окружности, построенной на треугольникипоявившихся в ходе триангуляции треугольников, критерий Делоне нарушаться не будетсодержаться точек).

Отсюда видно, что если случилось так, что у нас есть четыре или более точек, лежащих на одной окружности, то у построенной выпуклой оболочкиВоспользовавшись фактом выше, возможно, будут грани, не являющиеся треугольниками. Понятно, что такие грани будут выпуклыми многоугольниками. Тогда каждую из них можно затриангулировать [[Триангуляция полигонов приходим к очевидному решению как за <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 N \log(nN)) </tex>, где <tex>nN</tex> {{---}} количество точек.Триангуляция выпуклого многоугольника требует времени Удалить треугольники мы можем за <tex> \mathcal{O}(kN) </tex>, где <tex>k</tex> {{---}} число вершин с многоугольнике. Следовательно, в худшем случае нам потребуется суммарно Триангулиравать грани мы можем за <tex> \mathcal{O}(nN) </tex> операции, чтоб перетриангулировать все грани, оказавшиеся многоугольниками после построения выпуклой оболочкикак было показано выше.Таким образом, время работы всего алгоритма будет В результате получаем <tex> \mathcal{O}(n N \log(nN)) </tex>, ==Локальный критерий Делоне==

'''Глобальный Локальный критерий Делоне для ребра:''' при построении плоскости через ребро можно провести плоскость тактри точки, что все точки будут лежать образующие треугольник, противолежащие сторонам треугольника вершины соседей лежат ниже этой плоскости.

|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=Глобальный и локальный критерии Делоне для треугольника равносильны.

Предположим противноеИз глобального в локальный очевидно. Из локального в глобальный: Пусть выполняется локальный критерий, то есть для каждого треугольника мы можем провести плоскость, в секторе у ребра что соседние вершины для треугольника будут лежать не выше нашей плоскости.Но нашелся треугольник <tex>ABABC</tex> нашли множество точек из триангуляции, что для него не выполняется глобальный критерий, т. Треугольник е существует какая-то точка <tex>ADBE</tex> смежный, при том которая лежит выше плоскости <tex>ABC</tex>.В силу того, что локальный критерий выполняется, эта точка не принадлежит соседним треугольникам, в частности смежному треугольнику <tex>DABD</tex> по ребру <tex>AB</tex> За <tex>AB</tex> лежит под окружностью. Рассмотрим точку мы обозначили ребро, из которого видна точка <tex>E</tex> из того множества, т. Так как е такое ребро, что если провести сечение через точки <tex>ABA</tex> является пересечением плоскостей , <tex>ABCB</tex> и <tex>ADBO</tex>(центр окружности), то точка <tex>E</tex> содержится в полусфере, не содержащей треугольник <tex>ABC</tex>. Так как точка <tex>DE</tex> лежит под над плоскостью <tex>ABC</tex>, а точка <tex>ED</tex> над ней =под плоскостью <tex>ABC</tex> , то точка <tex>E</tex> лежит над плоскостью <tex>ADBABD</tex>. (с учетом того, что они лежат в одной полусфере, ребро AB общее и отделяет треугольник <tex>ABC</tex> от полусферы) (по утверждению выше) Посмотрим, существует ли у треугольника <tex>ABD</tex> смежный треугольник, содержащий вершину <tex>E</tex>:#Если треугольник он существует, то локальный критерий для треугольника <tex>AEDADE</tex> не выполняется. Противоречие.#Если он не существует, то повторим итерациюточка <tex>E</tex> так же будет лежать "над" каким-то смежным с <tex>ABD</tex> треугольником, иначе так как для треугольника <tex>ADBABD</tex> не будет будут выполняться те же условия, что и для <tex>ABC</tex>. Перейдем к такому треугольнику и повторим шаг. Заметим, что наш процесс есть локализация. Мы пустили луч (в ту сторону, где видим точку <tex>E</tex>) из исходного треугольника и идём вдоль него. В какой-то момент мы окажемся рядом с треугольником <tex>XYZ</tex>, для которого точка E выше плоскости, построенной на его трех точках, и в тоже время вершина E содержится в соседнем треугольнике, что нарушает локальный критерий. Противоречие. Значит глобальный критерий Делоне выполняется.

==Локальный критерий Критерии Делонедля ребер==

'''Локальный Глобальный критерий Делоне для ребра:''' через ребро можно провести плоскость так, что вершины, противолежащие этому ребру, все точки будут лежать ниже не выше этой плоскости.

'''Локальный критерий Делонедля ребра:''' при построении плоскости через три точкиребро можно провести плоскость так, образующие треугольникчто вершины, противолежащие сторонам треугольника вершины соседей лежат ниже этому ребру, будут лежать не выше этой плоскости.

Предположим противное, то есть найдётся такая плоскость, что вершины треугольников при ребре <tex>AB</tex> лежат под ней, но существует какая-то вершина <tex>F</tex> над ней. Проведём окружность с центром в сфере через <tex>AB</tex> и выберем треугольник лежащий в одной полусфере с точкой <tex>F</tex>, назовём его <tex>ABC</tex>. Точка <tex>E</tex> лежит над плоскостью Для треугольника <tex>ABC</tex> => <tex>F</tex> лежит внутри окружности около <tex>ABC</tex>. Возьмем треугольника при ребрене выполняется глобальный критерий Делоне, в чьем сегменте оказалась точка <tex>F</tex> поэтому воспользуемся алгоритмом из утверждения "Глобальный и локальный критерии Делоне равносильны" и назовем его найдем треугольник для которого не будет выполняться локальный критерий Делоне <tex>ABC\Rightarrow</tex>для одного из ребер найденного треугольника не выполняется локальный критерий Делоне. Если не существует смежный с ним треугольник при вершине <tex>F</tex>, то повторим итерацию!!!Следовательно, иначе противоречие с локальным критерием глобальный критерий Делонедля ребра выполняется.

 Обратно: Рассмотрим треугольник <tex>ABC</tex>, для каждого из ребра можно провести плоскость и они , такую что все точки будут лежать не выше её. Три плоскости образуют трехмерный угол, снаружи которого нет точек(снаружи == выше каждой плоскости при ребре). В пересечении угла и плосокости плоскости <tex>ABC</tex> образуется тетраэдр. Если в нем нет точек, значит точек нет и над плоскостью треугольника (точек снаружи тетраэдра нету), значит глобальный критерий выполняется. Проверим это. Пусть в нем есть точки, то тогда эти точки есть оказались внутри треугольника, тогда это не триангуляция => точек в тетраэдре нет => плоскостью <tex>ABC</tex> можно отделить пространство с точками => выполняется глобальный критерий.

[[Файл:file12345.png|400px|thumb|right|Красное ребро — до флипа, синее зеленое — после]]

Пусть мы вставляем точку <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>.

В самом начале для удобства реализации добавим к триангуляции центр сферы. Первую добавленную точку на сфере соединим с точкой <tex>O</tex>, вторую точку соединим с предыдущей точкой и центром сферы, третью - со всеми предыдущими. Получим выпуклое тело, далее точки вставляются либо на поверхность этого тела, либо за ее пределами. ==== Вставка точки, лежащей внутри триангуляции на поверхности сферы ====[[Файл:InsertAdd_into.jpg|left||Вставка внутрь треугольника]][[Файл:Add_on_edge.jpg|right||Вставка в треугольникна ребро треугольника]]

Итого у нас появилось несколько новых рёбер. Они все хорошие (по [[#newedgeslemma| лемме 7]]), плохими могут оказаться только рёбра, противолежащие вставленной точке. Флипаем рёбра, пока триангуляция не станет хорошей. ====Вставка точки, лежащей снаружи триангуляции====[[Файл:Insert.jpg|right||Вставка в треугольник]] Пусть мы добавляем точку <tex>P''</tex>. Нам нужно научиться вставлять точку в треугольник, одной из вершин которого является центр сферы. На самом деле, это теперь получится сделать естественным образом. Так как для определения принадлежности точки треугольнику на поверхности сферы мы смотрим на предикат поворота относительно плоскости, проходящей через центр сферы и ребро, и вставляемой точки <tex>P''</tex>, то для проверки попадания в треугольник, содержащий центр сферы достаточно проверить, что точка <tex>O</tex> видна из точки <tex>P''</tex>, т.е. точка <tex>P''</tex> находится по определенную сторону от плоскости, проходящей через ребро и точку <tex>O</tex>, и противоположенная вершина для ребра является центром сферы.        

==== Время работы ====

Переход. Пусть мы вставили точку <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>.

|id=vertex_st|statement=Математическое ожидание степени вершины после её вставки в триангуляцию Делоне равна равно <tex>O(1)</tex>.

<tex>E(\operatorname{deg}(v_{i+1}))=\frac {\sum_{p=\operatorname{perm}(v_0, v_1, ..., v_i)} \operatorname{deg} (p[i+1])} {(i+1)!}</tex>

Представим себе, что вместо того, чтобы удалять точку, мы просто опускаем ее во внутрь до тех пор, покаона пока она не перестает быть видимой в построенном на триангуляции многоугольнике. Предположим, что мы находимся в удаляемой точке, движемся в центр сферы и смотрим только в направлении движения.

Этот отрезок будет виден. Он не будет лежать на плоскосиплоскости. Он не будет лежать под плоскостью. Тогла получается, что он лежит над плоскостью(ближе к краю сферы), значит, многогранник был невыпуклый.

====Алгоритм удаления точки====

# Сделаем приоритетную очередь, в которой будем хранить пары отрезков, образующие ухо. Для этой очереди будем использовать TODO предикат, сортирующий уши в порядке, в котором они пересекают луч по направлению от удаляемой точки к центру сферы.

 =====Предикат=====[[Файл:sphere_del.png|400px|thumb|right| <tex> ABC</tex> {{---}} грань, <tex> O </tex> {{---}} центр сферы, <tex> P </tex> {{---}} удаляемая точка ]]При удалении точки, луч, исходящий из центра окружности в точку, пересекает плоскость очередной грани в некоторй точке <tex> T</tex>.Эту точку можно записать как <tex> T = O + kP </tex>, где <tex> O </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> ====Время работы====

|id=111

|id=212

<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>

|id=313|statement=Средняя степень точек на <tex>i</tex> уровне внутри окружности с центром в точке <tex>Q</tex> и проходящей через точку <tex>P_{i + 1}</tex>(ближайшая точка на <tex>i + 1</tex> уровне)равна <tex>O(1)</tex>

|aboutid=15|statement=13Степень ближайшей вершины <tex>O(1)</tex>|proof=Доказательство копирует случай на [[Триангуляция Делоне#nearestdegreelemma|плоскости]].}} {{Лемма|id=416