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

НЯ! Эта статья полна любви и обожания. Возможно, стоит добавить ещё больше?

Определение

Определение:

Триангуляция — набор непересекающихся отрезков, соединениющий заданный набор точек так, что добавление новых отрезков невозможно без пересечения уже имеющихся.

Определение:

Отрезок — кратчайшее расстояние от точки до точки на заданной поверхности.

Определение:

Симплекс(англ. simplex) — геометрическая фигура, являющаяся n-мерным обобщением треугольника.

Определение:

Триангуляция — разбиение геометрической фигуры на симплексы.

Определение:

Критерий Делоне: при построении плоскости через три точки, образующие треугольник, все остальные точки лежат ниже этой плоскости.

Существования триангуляции Делоне

Лемма (1):

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

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

[math]\triangleright[/math]

Пусть плоскость [math]\alpha[/math] пересекает сферу. Из центра [math]O[/math] опустим перпендикуляр [math]OC[/math] на плоскость [math]\alpha[/math]. Соединим произвольную точку [math]M[/math] линии пересения плоскости [math]\alpha[/math] со сферой с точками [math]O[/math] и [math]C[/math]. Так как [math]OC[/math] ⊥ [math]\alpha[/math], то [math]OC[/math] ⊥ [math]CM[/math]. В прямоугольном треугольнике [math]OCM CM2 = OM2 - OC2[/math]. Т.к. [math]OM[/math] и [math]OC[/math] - величины постоянные, то и [math]CM[/math] - величина постоянная. Таким образом все точки линии пересечения плоскости [math]\alpha[/math] и сферы равноудалены от точки [math]C[/math], поэтому эта линия пересечения является окружностью с центром в точке [math]C[/math] и радиусом [math]r = CM[/math].

[math]\triangleleft[/math]

Теорема:

Триангуляция Делоне существует, причём для каждого набора точек, в котором никакие четыре точки не лежат на одной окружности, она единственна.

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

[math]\triangleright[/math]

Построим выпуклую оболочку наших точек. Все грани выпуклой оболочки окажутся внутри сферы. Поскольку, все точки лежат на сфере, не найдётся точек, которые будут лежать за гранями выпуклой оболочки, иначе выпуклую оболочку можно было бы расширить. Таким образом, все точки, будут принадлежать выпуклой оболочке. Так же ясно,что критерий Делоне будет выполняться, поскольку для каждой грани не будет точек, которые лежат выше нее. Поскольку никакие четыре точки не лежат на одной окружности в исходном наборе точек, а значит, гранями выпуклой оболочки будут треугольнички. Значит, триангуляция существует. А поскольку выпуклая оболочка единственна, можно сказать,что и триангуляция единственна.

[math]\triangleleft[/math]

Лемма (2):

Гранями выпуклой оболочки будут выпуклые многоугольники

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

[math]\triangleright[/math]

По определению, мноожество является выпуклым, если для любых двух точек, отрезок, соединяющий эти точки, тоже входит во множество. И наша оболочка является выпуклой. Предположим, что грань выпуклой оболочки не выпуклый многоугольник. Тогда найдутся две точки, такие, что отрезок не лежит в грани. Тогда получается, что и вся оболочка не является выпуклой.

[math]\triangleleft[/math]

Если случилось так, что у нас есть четыре или более точек, лежащих на одной окружности, то у построенной выпуклой оболочки, возможно, будут грани, не являющиеся треугольниками. Понятно, что такие грани будут выпуклыми многоугольниками. Тогда каждую из них можно затриангулировать методом отрезания "ушей". Получившиеся треугольники будут лежать в одной плоскости и,следовательно, не будут нарушать критерий Делоне. В этом случае триангуляция может быть не единственна.

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

Алгоритм

Как следует из теоремы, для того, чтобы построить триангуляцию Делоне на множестве точек на сфере нам необходимо:

1. Построить выпуклую оболочку заданного набора точек
2. Пройтись по граням получившейся выпуклой оболочки и, если грань не является треугольником, то нужно затриангулировать ее как нибудь.

Время работы

Мы можем построить выпуклую оболочку за [math] \mathcal{O}(n \log(n)) [/math], где [math]n[/math] — количество точек. Триангуляция выпуклого многоугольника требует времени [math] \mathcal{O}(k) [/math], где [math]k[/math] — число вершин с многоугольнике. Следовательно, в худшем случае нам потребуется суммарно [math] \mathcal{O}(n) [/math] операции, чтоб перетриангулировать все грани, оказавшиеся многоугольниками после построения выпуклой оболочки. Таким образом, время работы всего алгоритма будет [math] \mathcal{O}(n \log(n)) [/math]

Критерий Делоне для ребер

Определение:

Глобальный критерий Делоне для ребра: через ребро можно провести плоскость так, что все точки будут лежать ниже этой плоскости.

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

Глобальный и локальный критерии Делоне для треугольника равносильны.

[math]\triangleright[/math]

Предположим противное, в секторе у ребра [math]AB[/math] нашли множество точек из триангуляции. Треугольник [math]ADB[/math] смежный, при том точка [math]D[/math] лежит под окружностью. Рассмотрим точку [math]E[/math] из того множества. Так как [math]AB[/math] является пересечением плоскостей [math]ABC[/math] и [math]ADB[/math], точка [math]D[/math] лежит под плоскостью [math]ABC[/math], а точка [math]E[/math] над ней => точка [math]E[/math] лежит над плоскостью [math]ADB[/math]. Если треугольник [math]AED[/math] не существует, то повторим итерацию, иначе для треугольника [math]ADB[/math] не будет выполняться локальный критерий.

[math]\triangleleft[/math]

Локальный критерий Делоне

Определение:

Локальный критерий Делоне для ребра: через ребро можно провести плоскость так, что вершины, противолежащие этому ребру, будут лежать ниже этой плоскости

Определение:

Локальный критерий Делоне: при построении плоскости через три точки, образующие треугольник, противолежащие сторонам треугольника вершины соседей лежат ниже этой плоскости.

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

Глобальный и локальный критерии Делоне для ребра равносильны.

[math]\triangleright[/math]

Из глобального в локальный очевидно, докажем обратно. Предположим противное, то есть найдётся такая плоскость, что вершины треугольников при ребре [math]AB[/math] лежат под ней, но существует какая-то вершина [math]F[/math] над ней. Проведём окружность с центром в сфере через [math]AB[/math] и выберем треугольник лежащий в одной полусфере с точкой [math]F[/math], назовём его [math]ABC[/math]. Точка [math]E[/math] лежит над плоскостью [math]ABC[/math] => [math]F[/math] лежит внутри окружности около [math]ABC[/math]. Возьмем треугольника при ребре, в чьем сегменте оказалась точка [math]F[/math] и назовем его [math]ABC[/math]. Если не существует смежный с ним треугольник при вершине [math]F[/math], то повторим итерацию, иначе противоречие с локальным критерием Делоне.

[math]\triangleleft[/math]

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

Критерии Делоне для ребер и треугольников равносильны.

[math]\triangleright[/math]

Из треугольника в ребра: если для каждого треугольника выполнен критерий, то для каждого ребра можно рассматривать плоскость при любом треугольнике при ребре. Обратно: Рассмотрим треугольник [math]ABC[/math], для каждого из ребра можно провести плоскость и они образуют трехмерный угол, снаружи которого нет точек. В пересечении угла и плосокости [math]ABC[/math] образуется тетраэдр. Если в нем есть точки, то точки есть внутри треугольника, тогда это не триангуляция => точек в тетраэдре нет => плоскостью [math]ABC[/math] можно отделить пространство с точками => выполняется глобальный критерий.

[math]\triangleleft[/math]

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

Определение:

Рассмотрим пару смежных треугольников. Рёбра этих треугольников образуют четырёхугольник с проведённой в нём диагональю. Операция замены этой диагонали на другую называется flip (флип).

Из леммы 3 следует, что если ребро плохое, то флип сделает его хорошим.

Красное ребро — до флипа, синее — после

Лемма (5):

Флип плохого ребра уменьшает разность объёмов сферы и выпуклого многогранника, построенного на точках с заданными ребрами.

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

[math]\triangleright[/math]

Рассмотрим два таких смежных треугольника, что ребро между ними является плохим.Четыре точки, принадлежащие смежным треугольникам, образуют тетраэдр. Проведём через какой-нибудь из двух треугольников плоскость. Вершина, противолежащая основанию тетраэдра, являющегося этим треугольником, лежит выше этой плоскости (так как для плохого ребра не выполняется локальный критерий Делоне), то есть тетраэдр не включается в объем фигуры. После флипа станет выполняться локальный критерий Делоне, то есть тело станет включать в себя тетраэдр. Поэтому после флипа плохого ребра объём тела увеличится на объём этого тетраэдра.

[math]\triangleleft[/math]

Лемма (6):

Флипами можно достичь хорошей триангуляции за конечное время.

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

[math]\triangleright[/math]

Всего триангуляций заданного множества точек конечное число, и среди них есть триангуляция Делоне. Последовательность флипов плохих рёбер триангуляции образует такую последовательность триангуляций, что разность объёмов сферы и многогранника, постоенного по триангуляции убывает (по лемме 5). Эта последовательность конечна (при этом последней в последовательности является триангуляция Делоне), значит, число флипов, требуемых для достижения триангуляции Делоне, тоже конечно.

[math]\triangleleft[/math]

Лемма (7):

Если в триангуляцию Делоне вставить точку в некоторый треугольник и соединить его вершины с этой точкой, то получившиеся рёбра будут хорошими.

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

[math]\triangleright[/math]

Пусть мы вставляем точку [math]P[/math]. Предположим, она была вставлена в треугольник [math]ABC[/math] не на ребро. Рассмотрим любое из рёбер — пусть это будет ребро [math]PC[/math]. Тогда проведем через точки [math]A[/math], [math]B[/math], [math]C[/math] плоскость [math]\alpha[/math], а так же проведем касательную плоскость [math]\beta[/math] к сфере через точку [math]C[/math]. Начнем уменьшать между этими плоскостями угол, двигая [math]\alpha[/math] к [math]\beta[/math]. В какой-то момент [math]\alpha[/math] пересечет точку [math]P[/math], а тогда мы предоставили плоскость, от которой все точки триангуляции находятся по одну сторону, так как изначально выше [math]\alpha[/math] была только точка [math]P[/math], а значит, ребро [math]PC[/math] удовлетворяет глобальному критерию Делоне. Аналогично для ребер [math]PA[/math] и [math]PB[/math]. Случай, когда точка вставляется на ребро, рассматривается аналогично.

[math]\triangleleft[/math]

Вставка точки

Лемма (О степени вершины):

Математическое ожидание степени вершины после её вставки в триангуляцию Делоне равна [math]O(1)[/math].

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

[math]\triangleright[/math]

Предположим, что мы вставляем [math]i+1[/math]-ую точку из последовательности из [math]n[/math] точек. Рассмотрим все перестановки из этих [math]i+1[/math] точек, означающие порядок вставки этих точек. Всего таких перестановок [math](i+1)![/math]. Тогда средняя степень последней вершины среди перестановок равна: [math]E(\operatorname{deg}(v_{i+1}))=\frac {\sum_{p=perm(v_0, v_1, ..., v_i)} \operatorname{deg} (p[i+1])} {(i+1)!}[/math] Каждая из [math]i+1[/math] вершин побывает последней ровно [math]i![/math] раз, поэтому: [math]E(\operatorname{deg} (v_{i+1}))=\frac {\sum_{k=0}^{i} i! \operatorname{deg} (v_k)} {(i+1)!} = \frac {\sum_{k=0}^i \operatorname{deg}(v_k)} {i+1}[/math] По лемме о рукопожатиях [math]\sum_{k=0}^{i} \operatorname{deg}(v_k) = 2D[/math], где [math]D[/math] - количество ребер. Следовательно: [math]E(\operatorname{deg} (v_{i+1}))=\frac {2D} {i+1}[/math] Триангуляция Делоне на сфере является планарным графом на сфере, чья укладка эквивалентна укладке на плоскости. Значит, для неё справедлива формула Эйлера: [math]V-D+F=2[/math], где [math]V[/math] - количество вершин, а [math]F[/math] - количество граней. Так как каждая грань образована тремя рёбрами, и при этом при подсчёте каждое ребро учитывается дважды, имеем: [math]3F=2D=\gt F=\frac {2D} {3}[/math]. Подставив в формулу Эйлера, получим: [math]V-D+\frac {2D} {3}=2=\gt \frac {1} {3}D=V-2=\gt D=3(V-2)=3((i+1)-2)=3(i-1)[/math] В итоге [math]E(\operatorname{deg} (v_{i+1}))=\frac {2D} {i+1}=\frac {6(i-1)} {i+1}=O(1)[/math].

[math]\triangleleft[/math]

Теорема:

При вставке точки в триангуляцию Делоне на сфере в среднем придётся сделать [math]O(1)[/math] флипов.

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

[math]\triangleright[/math]

Копирует случай на плоскости.

[math]\triangleleft[/math]

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

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

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

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