Изменения

|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>ABC</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>, вторую точку соединим с предыдущей точкой и центром сферы, третью - со всеми предыдущими. Получим выпуклое тело, которое будет шаровым сектором. Далее далее точки вставляются либо на поверхность этого тела, либо за ее пределами.

|id=111

|id=212

|id=313

|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>. Противоречие, значит такого быть не может.