Изменения

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

Удалить треугольники мы можем за <tex>\mathcal{O}(N)</tex>.Триангулиравать грани мы можем за <tex>\mathcal{O}(N)</tex> как было показано выше.

Предположим противное, то есть найдётся такая плоскость, что вершины треугольников при ребре <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>F</tex>, то повторим итерацию!!!Следовательно, иначе противоречие с локальным критерием глобальный критерий Делонедля ребра выполняется.

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

{{Утверждение|id=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>, вторую точку соединим с предыдущей точкой и центром сферы, третью - со всеми предыдущими. Получим выпуклое тело, далее точки вставляются либо на поверхность этого тела, либо за ее пределами. ==== Вставка точки, лежащей внутри триангуляции на поверхности сферы ====[[Файл: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>.

[[Файл:sphere_del.png|400px|thumb|right|<tex> ABC</tex> {{---}} грань, <tex> O </tex> {{---}} центр сферы, <tex> P </tex> {{---}} удаляемая точка ]]:: При удалении точки, луч, исходящий из центра окружности в точку, пересекает плоскость очередной грани в некоторй точке <tex> T</tex>.Эту точку можно записать как <tex>k T = O + kP </tex>, где <tex> O </tex> {{---\frac}} центр сферы, а <tex> p </tex> {{---}} удаляемая точка.Зпишем предикат при которм наша точка <tex>kP</tex> лежит на плоскости, проходящей через <tex>ABC</tex>:<tex>\begin{vmatrix} A & 1 \\ B & 1 \\ C & 1 \\ P kP & 0 1 \end{vmatrix}}{\begin{vmatrix} A \\ B \\ C \end{vmatrix}}= 0 </tex>

<tex>\begin{vmatrix} A & 1 \\ B & 1 \\ C & 1 \\ kP & 1 \end{vmatrix} + \begin{vmatrix} A \\ B \\ C \end{vmatrix} = 0 </tex>Тогда условие, по которому мы будем устанавливать порядок в приоритетной очереди будет::: <tex>\begin{vmatrix} A & 1 \\ B & 1 \\ C & 1 \\ kP & 1 \end{vmatrix} + \begin{vmatrix} A \\ B \\ C \end{vmatrix} k = \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 \endfrac{vmatrix} + \begin{vmatrix} a_x & a_y & a_z \\ b_x & b_y & b_z \\ c_x & c_y & c_z \end{vmatrix}</tex><tex> \Rightarrow </tex><tex>k\begin{vmatrix} A & 1 \\ B & 1 \\ C & 1 \\ P & 0 \end{vmatrix} + }{\begin{vmatrix} A \\ B \\ C \end{vmatrix} = 0}</tex>

|id=111

|id=212

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

|about=13|id=415|statement=Один уровень в среднем обрабатывается за Степень ближайшей вершины <tex>O(1)</tex>|proof=По Доказательство копирует случай на [[Триангуляция Делоне#2nearestdegreelemma|лемме 11плоскости]] алгоритм пройдет в среднем <tex>O(1)</tex> вершин, степень которых так же равна по [[#3|лемме 12]] <tex>O(1)</tex>, следовательно один уровень будет обработан за <tex>O(1)</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>. Противоречие, значит такого быть не может.