Изменения

Перейти к: навигация, поиск

Диаграмма Вороного

178 байт добавлено, 20 январь
Алгоритм Чана
=== Алгоритм Чана ===
Вершины проецируются из двумерной плоскости на поверхность параболоида (<tex>x, y</tex> остаются те же, добавляется <tex>z = x^2 + y^2</tex>). Далее по ним строится нижняя [[Статические_выпуклые_оболочки:_Джарвис,_Грэхем,_Эндрю,_Чен,_QuickHull|выпуклая нижняя оболочка]]. Поскольку параболоид выпуклый, на никакие вершины не будут удалены. На выходе получаются рёбра между вершинами, которые соответствуют триангуляции Делоне. Сложность работы - <tex>O(n \log n)</tex>.
== Диаграмма k-го порядка ==
Анонимный участник

Навигация