Изменения
→Статический алгоритм
{{Лемма
|about=1
|id=1|statement= Сечение сферы плоскостью есть кругокружность, а основание перпендикуляра, проведенного из центра шара к пересекаемой плоскости, есть центр кругаокружности, полученного полученной в сечении.
|proof=
[[Файл:drawing.png|400px|thumb|right|]]
{{Лемма
|about=2
|id=2
|statement= Гранями выпуклой оболочки будут выпуклые многоугольники
|proof=
===Время работы===
Мы можем построить выпуклую оболочку за <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>,
[[Файл:dol2.png|right]]
Из глобального в локальный очевидно, докажем обратно.
Предположим противное, то есть найдётся такая плоскость, что вершины треугольников при ребре <tex>AB</tex> лежат под ней, но существует какая-то вершина <tex>F</tex> над ней. Проведём окружность с центром в сфере через <tex>AB</tex> и выберем треугольник лежащий в одной полусфере с точкой <tex>F</tex>, назовём его <tex>ABC</tex>. Точка <tex>F</tex> лежит над плоскостью Для треугольника <tex>ABC</tex> не выполняется глобальный критерий Делоне, поэтому воспользуемся алгоритмом из утверждения "Глобальный и локальный критерии Делоне равносильны" и найдем треугольник для которого не будет выполняться локальный критерий Делоне <tex>\implies</tex> <tex>F</tex> лежит внутри окружности около <tex>ABCRightarrow</tex>для одного из ребер найденного треугольника не выполняется локальный критерий Делоне. Если не существует смежный с ним треугольник при вершине <tex>F</tex>, то повторим итерацию!!!Следовательно, иначе противоречие с локальным критерием глобальный критерий Делонедля ребра выполняется.
}}
{{Утверждение
Из треугольника в ребра: если для каждого треугольника выполнен критерий, то для каждого ребра можно рассматривать плоскость при любом треугольнике при ребре.
Обратно: Рассмотрим треугольник <tex>ABC</tex>, для каждого из ребра можно провести плоскость, такую что все точки будут лежать не выше её. Три плоскости образуют трехмерный угол, снаружи которого нет точек (снаружи == выше каждой плоскости при ребре). В пересечении угла и плосокости плоскости <tex>ABC</tex> образуется тетраэдр. Если в нем нет точек, значит точек нет и над плоскостью треугольника (точек снаружи тетраэдра нету), значит глобальный критерий выполняется. Проверим это.
Пусть в нем есть точки, тогда эти точки оказались внутри треугольника, тогда это не триангуляция.
}}
{{Лемма
|about=6
|id=6
|statement=
Флипами можно достичь хорошей триангуляции за конечное время.
|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>, вторую точку соединим с предыдущей точкой и центром сферы, третью - со всеми предыдущими. Получим выпуклое тело, которое будет шаровым сектором. Далее далее точки вставляются либо на поверхность этого тела, либо за ее пределами.
==== Вставка точки, лежащей внутри триангуляции ====
[[Файл:InsertAdd_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=8
|id=8
|statement=
При вставке точки будут флипаться только рёбра, противолежащие вставленной точке.
{{Лемма
|about=О степени вершины
|id=vertex_st
|statement=Математическое ожидание степени вершины после её вставки в триангуляцию Делоне равно <tex>O(1)</tex>.
|id=deglemma
{{Лемма
|about=9
|id=9
|statement=
Изначально нам будут видны грани, которые образуются внутри звездного многоугольника.
{{Лемма
|about=О количестве уровней
|id=10
|statement= Математическое ожидание уровней в локализационной структуре <tex> O(\log{n}) </tex>.
|proof= То же самое, что и для [[Триангуляция Делоне#levelslemma|плоскости]].
{{Лемма
|about=10
|id=111
|statement=Алгоритм найдет ближайшую точку
|proof=Допустим, что это не так. Это значит, что в внутри окружности с центром в точке <tex>Q</tex>, на которой лежит точка <tex>P</tex>, есть какие-то другие точки. То есть другими словами существует плоскость <tex>\alpha</tex> проходящая через точку <tex>P</tex>, выше которой находятся точка <tex>Q</tex>(так как она центр) и какие-то точки триангуляции.
{{Лемма
|about=11
|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>.
{{Лемма
|about=12
|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>.
{{Лемма
}}
{{Лемма
|id=16|statement=Точка на сфере может быть ближайшей для не более Один уровень в среднем обрабатывается за <tex>6O(1)</tex> точек.|proof=Пусть это не так. Тогда некоторая точка <tex>P</tex> является ближайшей для <tex>7</tex> точек: <tex>A_1 \dots A_7</tex>. Проведем отрезки По [[#2|лемме 11]] алгоритм пройдет в среднем <tex>O A_i</tex>. Получили семигранный угол. По свойствам многогранных углов: сумма их плоских углов не превосходит <tex>360</tex>. Проведем <tex>7</tex> полуплоскостей с основанием <tex>OP(1)</tex>вершин, каждая из степень которых содержит соответствующий отрезок <tex>O A_i</tex>. Плоский угол так же равна по [[#3|лемме 12]] <tex>A_i O A_{i + (1})</tex> не меньше угла между полуплоскостями, содержащими отрезки <tex>O A_i</tex> и следовательно один уровень будет обработан за <tex>O A_{i + (1}</tex>. Тогда так как сумма углов между полуплоскостями равна <tex>360</tex>, получаем, что сумма плоских углов в семигранном угле не менее <tex>360)</tex>. Противоречие, значит такого быть не может.
}}
{{Лемма
|id=17
|statement=На втором этапе алгоритма луч в среднем пересечет <tex>O(1)</tex> ребер.
|proof=Рассмотрим окружность с центром в точке <tex>Q</tex>, проходящую через ближайшую для неё точку триангуляции <tex>P_{i + 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>. Противоречие.
}}
