Триангуляция Делоне на Сфере

Динамический алгоритм

Локализация в триангуляции

Построим алгоритм на сфере по аналогии с плоскостью.

Структура данных

Локализационная структура состоит из нескольких уровней, где каждый уровень — триангуляция Делоне. На нижнем уровне содержатся все точки. Далее точка с вероятностью [math] p [/math] попадает на следующий уровень. Если на последнем уровне находится одна точка, то дальше она уже не пойдет.

Лемма (О количестве уровней):

Математическое ожидание уровней в локализационной структуре [math] O(\log{n}) [/math].

Доказательство:

[math]\triangleright[/math]

То же самое, что и для плоскости.

[math]\triangleleft[/math]

Утверждение:

Локализационная структура занимает [math] O(n) [/math] памяти.

[math]\triangleright[/math]

Опять же доказательство копируется с плоскости.

[math]\triangleleft[/math]

Принадлежность треугольнику

Пусть даны точки [math]P[/math], [math]A[/math], [math]B[/math], [math]C[/math] на сфере с центром [math]O[/math], тогда [math]P[/math] принадлежит треугольнику [math]ABC[/math], тогда и только тогда, когда поворот [math]P[/math] относительно плоскостей [math]AOB[/math], [math]BOC[/math], [math]COA[/math] одинаковый.

Алгоритм

Чтобы найти треугольник, которому принадлежит точка запроса(точка [math]Q[/math]), сначала найдем ближайшую к ней точку триангуляции(точка [math]P[/math]), а зачем вдоль луча [math]PQ[/math] будем обходить треугольники, пока не локализуемся.

Поиск точки [math]P[/math]:

• На последнем уровне нашей структуры находиться [math]O(1)[/math] точек, поэтому просто переберем эти точки и найдем ближайшую к [math]Q[/math].
• При переходе с [math]i + 1[/math] уровня на [math]i[/math] новая ближайшая точка [math]V_i[/math] может быть только внутри окружности с центром в точке [math]Q[/math] проходящей через точку [math]V_{i + 1}[/math](ближайшая точка на [math]i + 1[/math] уровне). Переберем всех соседей точки [math]V_{i + 1}[/math] и выберем ближайшего к точке [math]Q[/math]. Повторяем эту операцию, пока можем приближаться к точке запроса.

Лемма (1):

Алгоритм найдет ближайшую точку

Доказательство:

[math]\triangleright[/math]

Допустим, что это не так. Это значит, что в внутри окружности с центром в точке [math]Q[/math], на которой лежит точка [math]P[/math], есть какие-то другие точки. То есть другими словами существует плоскость [math]\alpha[/math] проходящая через точку [math]P[/math], выше которой находятся точка [math]Q[/math](так как она центр) и какие-то точки триангуляции. Проведем в точке [math]P[/math] касательную плоскость [math]\beta[/math] к сфере. Очевидно, что она делит всё пространство на [math]2[/math] части: в первой нет никаких точек, а во второй находятся все точки триангуляции. Пусть между плоскостями [math]\alpha[/math] и [math]\beta[/math] угол [math]\gamma[/math]. Начнем его уменьшать, то есть поворачивать плоскость [math]\beta[/math]. Очевидно, что она начнет пересекать сферу, тогда она будет соответствовать какой-то окружности на сфере. При этом все точки сферы, которые выше плоскости [math]\beta[/math] будут выше плоскости [math]\alpha[/math], значит это будет вложенная окружность. Будем уменьшать угол [math]\gamma[/math] до того момента, когда какая-то точка [math]P'[/math], лежащая внутри окружности(такая есть по предположению), не станет принадлежать плоскости [math]\beta[/math]. В этот момент выше плоскости [math]\beta[/math] нет ни одной точки из триангуляции. Значит для ребра [math]PP'[/math] можно провести окружность, не содержащую других точек, то есть выполняется глобальный критерий Делоне. Значит в триангуляции должно быть ребро [math]PP'[/math], и по алгоритму мы должны были его перебрать и увидеть, что [math]P'[/math] ближе к точке [math]Q[/math] и перейти к ней. Получили противоречие, значит алгоритм правильно находит ближайшую точку.

[math]\triangleleft[/math]

Лемма (2):

Среднее число точек, лежащих внутри окружности с центром в точке [math]Q[/math] и проходящей через точку [math]V_{i + 1}[/math] равно [math]O(1)[/math].

Доказательство:

[math]\triangleright[/math]

Рассмотрим точки триангуляции [math]\{A_i\}[/math]. Для каждой точки [math] A_i[/math] проведем окружность с центром в ней, проходящую через ближайшую к ней точку. Посчитаем во сколько окружностей в среднем попадет точка какая-то точка [math]U[/math]. Проведем через [math]OU[/math] три плоскости так, чтобы они делили всё пространство на [math]6[/math] равных частей. Покажем, что в одной части [math]O(1)[/math] окружностей будут включать в себя точку [math]U[/math], тогда всего таких окружностей будет тоже [math]O(1)[/math]. Рассмотрим одну часть. Отсортируем точки, которые ей принадлежат, по степени удаленности от точки [math]U[/math]. Окрасим точки в два цвета: красный — точки с [math]i[/math] уровня черный — точки с [math]i + 1[/math] уровня Если на [math]j[/math]-ой позиции находится черная точка, то точки с индексом [math]j + 1[/math] и далее не будут содержать в окружности точку [math]U[/math](потому что [math]j[/math] была ближайшей на предыдущем уровне из этой части пространства). Тогда если [math] X [/math] — количество окружностей, которым принадлежит точка [math]U[/math], то так как точка проходит на следующий уровень с вероятностью [math]p[/math]: [math]E(X) \leqslant \sum\limits_{i = 1\dots\infty}{i \cdot p(1 - p) ^ i} = [/math] [math]\sum\limits_{i = 1\dots\infty}{\sum\limits_{j = i\dots\infty}{p (1 - p) ^ j}} = [/math] [math]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)[/math] Получается, что каждая точка принадлежит [math]O(1)[/math], следовательно внутри каждой окружности содержит [math]O(1)[/math] точек.

[math]\triangleleft[/math]

Лемма (3):

Средняя степень точек на [math]i[/math] уровне внутри окружности с центром в точке [math]Q[/math] и проходящей через точку [math]P_{i + 1}[/math](ближайшая точка на [math]i + 1[/math] уровне)

Доказательство:

[math]\triangleright[/math]

Пусть есть функция [math]circle(q, p, i)[/math], возвращающая [math]1[/math], если точка [math]p[/math] принадлежит окружности с центром в точке [math]q[/math], проходящую через ближайшую к [math]q[/math] на [math]i[/math] уровне точку, а иначе [math]0[/math]. Пусть [math]Points_i[/math] — множество точек на [math]i[/math]-ом уровне. [math]X[/math] — степень вершины внутри окружности, тогда: [math]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|} =[/math] Меняем порядок суммирования, и получаем: [math]= \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[/math] По предыдущей лемме получаем: [math]\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[/math] [math]\approx \dfrac{\sum\limits_{p \in Points_{i - 1}}{deg(p)}}{\left| Points_{i - 1} \right|} = \dfrac{O(n)}{n} = O(1)[/math]

[math]\triangleleft[/math]

Лемма (4):

Один уровень в среднем обрабатывается за [math]O(1)[/math]

Доказательство:

[math]\triangleright[/math]

По лемме 2 алгоритм пройдет в среднем [math]O(1)[/math] вершин, степень которых так же равна по лемме 3 [math]O(1)[/math], следовательно один уровень будет обработан за [math]O(1)[/math].

[math]\triangleleft[/math]

Теорема (Следствие):

Локализация в среднем работает за [math]O(\log{n})[/math]