355
правок
Изменения
м
→Вставка точки, лежащей снаружи триангуляции
Среднее число флипов — <tex>O(1)</tex> ({{TODO|t=Доказать, почему}}). Поэтому время вставки целиком зависит от времени локализации.
==== Вставка точки, лежащей снаружи триангуляции ====
Представим, что вне триангуляции — бесконечные треугольники, основания которых — рёбра выпуклой оболочки триангуляции, а противолежащая ребру вершина — это бесконечно удалённая точка. Тогда понятно, что вставка точки, не лежащей в триангуляции, сведётся к вставке точки внутрь триангуляции, если мы научимся обрабатывать бесконечные фейсы.
{{TODO|t=Написать про бесконечно удалённую точку}}
