212
правок
Изменения
Нет описания правки
Триангуляция выпуклого многоугольника требует времени <tex> \mathcal{O}(k) </tex>, где <tex>k</tex> {{---}} число вершин с многоугольнике. Следовательно, в худшем случае нам потребуется суммарно <tex> \mathcal{O}(n) </tex> операции, чтоб перетриангулировать все грани, оказавшиеся многоугольниками после построения выпуклой оболочки.
Таким образом, время работы всего алгоритма будет <tex> \mathcal{O}n \log(n) </tex>
=Динамический алгоритм=
==Локализация в триангуляции==
Построим алгоритм на сфере по аналогии с плоскостью.
===Структура данных===
Локализационная структура состоит из нескольких уровней, где каждый уровень {{---}} триангуляция Делоне. На нижнем уровне содержатся все точки. Далее точка с вероятностью <tex> p </tex> попадает на следующий уровень. Если на последнем уровне находится одна точка, то дальше она уже не пойдет.
{{Лемма
|about=О количестве уровней
|statement= Математическое ожидание уровней в локализационной структуре <tex> O(\log{n}) </tex>.
|proof= То же самое, что и для [[Триангуляция Делоне#levelslemma|плоскости]].
}}
{{Утверждение
|statement= Локализационная структура занимает <tex> O(n) </tex> памяти.
|proof= Опять же доказательство копируется с плоскости.
}}
===Принадлежность треугольнику===
Пусть даны точки <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> будем обходить треугольники, пока не локализуемся.
Поиск точки <tex>P</tex>:
* На последнем уровне нашей структуры находиться <tex>O(1)</tex> точек, поэтому просто переберем эти точки и найдем ближайшую к <tex>Q</tex>.
* При переходе с <tex>i + 1</tex> уровня на <tex>i</tex> новая ближайшая точка <tex>V_i</tex> может быть только внутри окружности с центром в точке <tex>Q</tex> проходящей через точку <tex>V_{i + 1}</tex>(ближайшая точка на <tex>i + 1</tex> уровне). Переберем всех соседей точки <tex>V_{i + 1}</tex> и выберем ближайшего к точке <tex>Q</tex>. Повторяем эту операцию, пока можем приближаться к точке запроса.
{{Лемма
|about=1
|id=1
|statement=Алгоритм найдет ближайшую точку
|proof=Допустим, что это не так. Это значит, что в внутри окружности с центром в точке <tex>Q</tex>, на которой лежит точка <tex>P</tex>, есть какие-то другие точки. То есть другими словами существует плоскость <tex>\alpha</tex> проходящая через точку <tex>P</tex>, выше которой находятся точка <tex>Q</tex>(так как она центр) и какие-то точки триангуляции.
Проведем в точке <tex>P</tex> касательную плоскость <tex>\beta</tex> к сфере. Очевидно, что она делит всё пространство на <tex>2</tex> части: в первой нет никаких точек, а во второй находятся все точки триангуляции.
Пусть между плоскостями <tex>\alpha</tex> и <tex>\beta</tex> угол <tex>\gamma</tex>. Начнем его уменьшать, то есть поворачивать плоскость <tex>\beta</tex>. Очевидно, что она начнет пересекать сферу, тогда она будет соответствовать какой-то окружности на сфере. При этом все точки сферы, которые выше плоскости <tex>\beta</tex> будут выше плоскости <tex>\alpha</tex>, значит это будет вложенная окружность.
Будем уменьшать угол <tex>\gamma</tex> до того момента, когда какая-то точка <tex>P'</tex>, лежащая внутри окружности(такая есть по предположению), не станет принадлежать плоскости <tex>\beta</tex>. В этот момент выше плоскости <tex>\beta</tex> нет ни одной точки из триангуляции. Значит для ребра <tex>PP'</tex> можно провести окружность, не содержащую других точек, то есть выполняется глобальный критерий Делоне. Значит в триангуляции должно быть ребро <tex>PP'</tex>, и по алгоритму мы должны были его перебрать и увидеть, что <tex>P'</tex> ближе к точке <tex>Q</tex> и перейти к ней. Получили противоречие, значит алгоритм правильно находит ближайшую точку.
}}
{{Лемма
|about=2
|id=2
|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>OU</tex> три плоскости так, чтобы они делили всё пространство на <tex>6</tex> равных частей. Покажем, что в одной части <tex>O(1)</tex> окружностей будут включать в себя точку <tex>U</tex>, тогда всего таких окружностей будет тоже <tex>O(1)</tex>.
Рассмотрим одну часть. Отсортируем точки, которые ей принадлежат, по степени удаленности от точки <tex>U</tex>. Окрасим точки в два цвета:
* красный {{---}} точки с <tex>i</tex> уровня
* черный {{---}} точки с <tex>i + 1</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_{i = 1\dots\infty}{i \cdot p(1 - p) ^ i} = </tex>
<tex dpi = 150>\sum\limits_{i = 1\dots\infty}{\sum\limits_{j = i\dots\infty}{p (1 - p) ^ j}} = </tex>
<tex dpi = 150>p\sum\limits_{i = 1\dots\infty}{(1-p)^i \cdot (\sum\limits_{j = 0\dots\infty}{(1 - p) ^ j})} = \sum\limits_{i = 1\dots\infty}{(1-p)^i} = \frac{1-p}{p} = O(1)</tex>
Получается, что каждая точка принадлежит <tex>O(1)</tex>, следовательно внутри каждой окружности содержит <tex>O(1)</tex> точек.
}}
{{Лемма
|about=3
|id=3
|statement=Средняя степень точек на <tex>i</tex> уровне внутри окружности с центром в точке <tex>Q</tex> и проходящей через точку <tex>P_{i + 1}</tex>(ближайшая точка на <tex>i + 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>.
Пусть <tex>Points_i</tex> {{---}} множество точек на <tex>i</tex>-ом уровне.
<tex>X</tex> {{---}} степень вершины внутри окружности, тогда:
<tex dpi = 130>E(X) = \dfrac{\sum\limits_{q \in Points_{i - 1}}{\sum\limits_{p \in Points_{i - 1}}{circle(q, p, i) \cdot deg(p)}}}{\left| Points_{i - 1} \right|} =</tex>
Меняем порядок суммирования, и получаем:
<tex dpi = 130>= \dfrac{\sum\limits_{p \in Points_{i - 1}}{deg(p) \sum\limits_{q \in Points_{i - 1}}{circle(q, p, i)}}}{\left| Points_{i - 1} \right|} \leqslant</tex>
По предыдущей лемме получаем:
<tex dpi = 130>\leqslant \dfrac{\sum\limits_{p \in Points_{i - 1}}{deg(p) \sum\limits_{1 \dots \infty}{i \cdot p \cdot (1 - p) ^ i}}}{\left| Points_{i - 1} \right|} \approx</tex>
<tex dpi = 130>\approx \dfrac{\sum\limits_{p \in Points_{i - 1}}{deg(p)}}{\left| Points_{i - 1} \right|} = \dfrac{O(n)}{n} = O(1)</tex>
}}
{{Лемма
|about=4
|id=4
|statement=Один уровень в среднем обрабатывается за <tex>O(1)</tex>
|proof=По [[#2|лемме 2]] алгоритм пройдет в среднем <tex>O(1)</tex> вершин, степень которых так же равна по [[#3|лемме 3]] <tex>O(1)</tex>, следовательно один уровень будет обработан за <tex>O(1)</tex>.
}}
{{Теорема
|about=Следствие
|statement=Локализация в среднем работает за <tex>O(\log{n})</tex>
}}
