Изменения
→Построение: А что про Форчуна и Чана ничего не написано? Добавил. Если у кого есть желание - дополните и приведите к нормальному виду.
|[[Файл:voronoi-update-dcel.png|400px|thumb|Обновление структуры при добавлении ребра]]
|}
=== Алгоритм Форчуна ===
Построение производится при помощи заметающей прямой и парабол позади неё (параболы в данном случае - это множества точек, равноудалённых от вершины и прямой). Сама диаграмма "рисуется" местами соприкасания соседних парабол. Несмотря на то, что в теории движение прямой происходит непрерывно, сам алгоритм обрабатывает только крайние случаи, когда происходят события. Рассматривается 2 типа событий - появление новой параболы, когда заметающая прямая касается вершины, и схлопывание параболы - когда две соседние параболы её полностью накрывают. Всего событий <tex>O(n)</tex> (<tex>n</tex> - число вершин). Для каждого события вычисляется его время (позиция заметающей прямой), события кладутся в очередь с приоритетом (отсюда <tex>O(\log n)</tex> по времени) и обрабатываются, пока очередь непуста. При обработке событий также записываются пары взаимодействующих вершин (у которых сайты имеют общую границу), это и является результатом работы алгоритма.
Сложность работы алгоритма - <tex>O(n \log n)</tex> по времени и <tex>O(n)</tex> по памяти.
Более подробно:
* [https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A4%D0%BE%D1%80%D1%87%D1%83%D0%BD%D0%B0 Описание алгоритма на Wikipedia]
* [https://www2.cs.sfu.ca/~binay/813.2011/Fortune.pdf Презентация с описанием в деталях]
=== Алгоритм Чана ===
Вершины проецируются из двумерной плоскости на поверхность параболоида (<tex>x, y</tex> остаются те же, добавляется <tex>z = x^2 + y^2</tex>). Далее по ним строится [[Статические_выпуклые_оболочки:_Джарвис,_Грэхем,_Эндрю,_Чен,_QuickHull|выпуклая нижняя оболочка]], на выходе получаются рёбра между вершинами, которые соответствуют триангуляции Делоне.
== Диаграмма k-го порядка ==
