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

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

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

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

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

Локализационная структура состоит из нескольких уровней, где каждый уровень — триангуляция Делоне. На нижнем уровне содержатся все точки. Далее точка с вероятностью [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]. Повторяем эту операцию, пока можем приближаться к точке запроса.

Лемма:

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

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

[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]