355
правок
Изменения
м
Нет описания правки
<tex>(\vec O + \vec{r_x}, (\vec O + \vec{r_x})^2) = (\vec O + \vec{r_x}, \vec O^2 + \vec{r_x}^2 + 2\vec O \vec {r_x}) = (\vec O + \vec{r_x}, \vec O^2 + (tR)^2 + 2\vec O \vec {r_x})</tex>
{{Acronym|Так как <tex>\{r_i\}</tex> афинно независимы, то <tex>r_x</tex> можно представить как <tex>r_x = \sum_{i=1}^{n+1}\alpha_i r_i</tex>, причём <tex>\sum_{i=1}^{n+1}\alpha_i = 1</tex>|Общеизвестный факт}}.
Запишем определитель, показывающий положение точки <tex>x</tex> на параболоиде относительно плоскости, заданной точками <tex>\{a_i\}</tex>:
При удалении точки получится {{Acronym|звёздный многоугольник, который можно затриангулировать за линию|Почему на эту тему нет конспекта? Я не собираюсь тут это доказывать}}. Дальше по традиции флипаем всё, что могло стать плохим, пока не получим хорошую триангуляцию.
{{Acronym|Средняя степень вершины в триангуляции — <tex>O(1)</tex> ({{TODO|t=Почему?}} — почти то, что нужно, здесь [http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9A%D0%B8%D1%80%D0%BA%D0%BF%D0%B0%D1%82%D1%80%D0%B8%D0%BA%D0%B0_%D0%B4%D0%B5%D1%82%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8_%D1%82%D1%80%D0%B8%D0%B0%D0%BD%D0%B3%D1%83%D0%BB%D1%8F%D1%86%D0%B8%D0%B8#.D0.92.D1.8B.D0.B1.D0.BE.D1.80_.D0.BC.D0.BD.D0.BE.D0.B6.D0.B5.D1.81.D1.82.D0.B2.D0.B0_.D1.83.D0.B4.D0.B0.D0.BB.D1.8F.D0.B5.D0.BC.D1.8B.D1.85_.D0.B2.D0.B5.D1.80.D1.88.D0.B8.D0.BD]. Потом пишем <tex>\sum_{v \in V}{deg(v)} = 2E</tex>, делим на <tex>|V|</tex> и получаем <tex>avg(deg(v)) = \frac{O(|V|)Общеизвестный факт}{|V|} = O(1)</tex>), поэтому триангуляция звёздного многоугольника будет тоже за <tex>O(1)</tex>. С флипами всё тоже, в общем-то, хорошо. Итого удаление точки работает за <tex>O(1)</tex>.
== Локализационная структура ==
