1632
правки
Изменения
м
rollbackEdits.php mass rollback
|proof=[[Файл:voronoi-circles.png|200px|right]]Предположим, что <tex>q</tex> существует. Тогда, так как <tex>C_P(q)</tex> не содержит в себе сайтов и содержит <tex>p_i, \ p_j</tex> на границе, <tex> \rho(q, p_i) = \rho(q, p_j) \leqslant \rho(q, p_k), \ 1 \leqslant k \leqslant n</tex>. Отсюда выходит, что <tex>q</tex> — вершина <tex>Vor(P)</tex> или лежит на ребре диаграммы. Но по предыдущей лемме выходит, что <tex>q</tex> не может быть вершиной диаграммы. Значит, она лежит на ребре, заданном серединным перпендикуляром к <tex>p_i p_j</tex>.
Докажем в другую сторону: пусть серединный перпендикуляр к <tex>p_i p_j</tex> задаёт ребро диаграммы. Наибольшая пустая окружность любой точки <tex>q</tex> на этом ребре должна содержать на границе <tex>p_i</tex> и <tex>p_j</tex> (так как <tex>q</tex> равноудалена от <tex>p_i</tex> и <tex>p_j</tex>). Также эта окружность не должна содержать никаких других сайтов на границе, так как тогда она не является вершиной.
}}
|[[Файл: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|выпуклая оболочка]]. Поскольку параболоид выпуклый, никакие вершины не будут удалены. На выходе получаются рёбра между вершинами, которые соответствуют триангуляции Делоне. Сложность работы - <tex>O(n \log n)</tex>.
== Диаграмма k-го порядка ==
* [http://students.info.uaic.ro/~emilian.necula/vor2.pdf Algorithms for constructing Voronoi diagrams, Vera Sacrist´an {{---}} Incremental algorithm]
* [http://en.wikipedia.org/wiki/Voronoi_diagram Wikipedia — Voronoi diagram]
* [https://web.archive.org/web/20170329014016/http://www.cs.uu.nl/docs/vakken/ga/slides7b.pdf Computational Geometry {{---}} Lecture 13: More on Voronoi diagrams]
[[Категория: Вычислительная геометрия]]
[[Категория: Триангуляция Делоне и диаграмма Вороного]]
