212
правок
Изменения
Новая страница: «=Динамический алгоритм= ==Локализация в триангуляции== Построим алгоритм на сфере по анал...»
=Динамический алгоритм=
==Локализация в триангуляции==
Построим алгоритм на сфере по аналогии с плоскостью.
===Структура данных===
Локализационная структура состоит из нескольких уровней, где каждый уровень {{---}} триангуляция Делоне. На нижнем уровне содержатся все точки. Далее точка с вероятностью <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>. Повторяем эту операцию, пока можем приближаться к точке запроса.
{{Лемма
|statement=Алгоритм найдет ближайшую точку
|proof=Допустим, что это не так. Это значит, что в внутри окружности с центром в точке <tex>Q</tex>, на которой лежит точка <tex>P</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>. Повторяем эту операцию, пока можем приближаться к точке запроса.
{{Лемма
|statement=Алгоритм найдет ближайшую точку
|proof=Допустим, что это не так. Это значит, что в внутри окружности с центром в точке <tex>Q</tex>, на которой лежит точка <tex>P</tex>, есть какие-то другие точки.
}}
