355
правок
Изменения
м
→Локализационная структура
== Локализационная структура ==
=== Сама структура Cтруктура ===В общем-тоЛокализационная структура состоит из нескольких уровней, довольно стандартная схема для рандомизированных структур: на где каждый уровень — это триангуляция Делоне. На нижнем уровне содержатся все точки; каждая . Каждая точка с вероятностью <tex>p </tex> проходит на следующий уровень(причём если точка — единственная на последнем уровне, то дальше она не пройдёт). Уровни связаны между собой следующим образом: на уровне <tex>i</tex> каждая точка содержит указатель на себя же на уровне <tex>i-1</tex>.=== Локализация Алгоритм локализации ===
Как происходит локализация: нам дают точку <tex>v_{i+1}</tex>, которая на предыдущем уровне была ближайшей к точке <tex>q</tex>, которую мы локализуем. Нужно получить следующую точку <tex>v_i</tex>, которая будет ближайшей уже на этом уровне. Делается это следующим образом:
* Находим, в каком из треугольников, смежных с <tex>v_{i+1}</tex>, лежит отрезок <tex>v_{i+1} q</tex>
{{TODO|t=Картинку для ясности}}
Предположим, что это не так. Назовём локализуемую точку <tex>q</tex>, а последнего кандидата на то, чтобы быть ближайшей точкой — <tex>v</tex>. Раз эта точка на самом деле не ближайшая, то в окружности, проходящей через <tex>v</tex>, с центром в точке <tex>q</tex> найдутся ещё какие-то точки, не смежные с <tex>v</tex>. Рассмотрим ближайшую из них к <tex>v</tex>: точку <tex>v'</tex>. Построим на <tex>vv'</tex> окружность как на диаметре. В этой окружности не будет лежать никаких точек, так как мы взяли ближайшую. Значит, ребро <tex>vv'</tex> удовлетворяет критерию Делоне и должно являться ребром триангуляции, но по предположению этого ребра нет. Значит, предположение неверно.
{{TODO|t=Кажется, тут какая-то бага}}
}}
=== Профит Время работы, требуемая память ===
{{TODO|t=Время работы, требуемая память}}
