Триангуляция Делоне на Сфере — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритм)
 
(не показаны 2 промежуточные версии этого же участника)
Строка 18: Строка 18:
  
 
===Принадлежность треугольнику===
 
===Принадлежность треугольнику===
Пусть дана точки <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>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> одинаковый.
  
 
===Алгоритм===
 
===Алгоритм===
Строка 29: Строка 29:
  
 
{{Лемма
 
{{Лемма
 +
|about=1
 +
|id=1
 
|statement=Алгоритм найдет ближайшую точку
 
|statement=Алгоритм найдет ближайшую точку
 
|proof=Допустим, что это не так. Это значит, что в внутри окружности с центром в точке <tex>Q</tex>, на которой лежит точка <tex>P</tex>, есть какие-то другие точки. То есть другими словами существует плоскость <tex>\alpha</tex> проходящая через точку <tex>P</tex>, выше которой находятся точка <tex>Q</tex>(так как она центр) и какие-то точки триангуляции.  
 
|proof=Допустим, что это не так. Это значит, что в внутри окружности с центром в точке <tex>Q</tex>, на которой лежит точка <tex>P</tex>, есть какие-то другие точки. То есть другими словами существует плоскость <tex>\alpha</tex> проходящая через точку <tex>P</tex>, выше которой находятся точка <tex>Q</tex>(так как она центр) и какие-то точки триангуляции.  
Строка 34: Строка 36:
 
Пусть между плоскостями <tex>\alpha</tex> и <tex>\beta</tex> угол <tex>\gamma</tex>. Начнем его уменьшать, то есть поворачивать плоскость <tex>\beta</tex>. Очевидно, что она начнет пересекать сферу, тогда она будет соответствовать какой-то окружности на сфере. При этом все точки сферы, которые выше плоскости <tex>\beta</tex> будут выше плоскости <tex>\alpha</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> и перейти к ней. Получили противоречие, значит алгоритм правильно находит ближайшую точку.
 
Будем уменьшать угол <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>
 
}}
 
}}

Текущая версия на 00:52, 21 ноября 2016

Динамический алгоритм[править]

Локализация в триангуляции[править]

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

Структура данных[править]

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