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