Изменения

Есть множество точек <tex>P</tex> на плоскости. Кусочек плоскости из точек <tex>q</tex> такой, что для всех <tex>q</tex> ближайшей точкой из множества <tex>P</tex> является одна и та же точка <tex>p</tex>, называется ячейкой Вороного точки <tex>p</tex>. Разбиение плоскости на такие ячейки для всех точек <tex>p_i \in P</tex> называется диаграммой Вороного для множества <tex>P</tex>.

В зависимости от контекста будем называть диаграммой Вороного как разбиение на ячейки, так и составляющие [[Основные определения теории графов|граф]] из вершин и рёбер, составляющих эти ячейки вершины и рёбра.

=== Количество вершин и рёбер в ячейке Связь с пересечением полуплоскостей ===Возьмём две точки плоскости: <tex>p</tex> и <tex>q</tex>. Проведём серединный перпендикуляр к отрезку <tex>pq</tex>; полученную полуплоскость, которая содержит в себе <tex>p</tex>, обозначим <tex>h(p, q)</tex>, другую — <tex>h(q, p)</tex>. Заметим, что для точки <tex>r</tex> выполняется <tex>r \in h(p, q)</tex> тогда и только тогда, когда <tex>\rho(r, p) < \rho(r, q)</tex>. Отсюда вытекает следующее:

|statement=<tex>\mathcal{V}(p_i) = \cap_bigcap\limits_{1 \leqslant j \leqslant n, j \neq i} h(p_i, p_j)</tex>

Отсюда получаем, что что ячейка Вороного — это пересечение <tex>n - 1</tex> полуплоскостей, и поэтому представляет собой (возможно, неограниченную) открытую выпуклую область с не более чем <tex>n - 1</tex> вершинами и <tex>n - 1</tex> рёбрами.

=== Отсутствие прямых в общем случае Топология диаграммы Вороного ===

|proof=[[Файл:voronoi-not-lines.png|200px|thumb|right]] В случае, если все сайты лежат на одной прямой, каждая пара соседних сайтов порождает серединный перпендикуляр к отрезку, содержащему их, и, соответственно, к прямой, которая содержит все сайты. Так получаются <tex>n - 1</tex> прямая, каждая из которых перпендикулярна прямой, содержащей сайты, а значит, эти прямые параллельны.

Докажем теперь, что диаграмма связна. Предположим, что это не так. Тогда на её рёбрах найдутся две точки <tex>s</tex> и <tex>t</tex>, между которыми нет пути по рёбрам диаграммы. Рассмотрим отрезок <tex>st</tex>. Он пересекает некоторое количество ячеек диаграммы, . Пусть он пересекает какую-то ячейку в точках <tex>a</tex> и <tex>b</tex>. От точки <tex>a</tex> до точки <tex>b</tex> можно добраться по рёбрам тогда итолько тогда, раз когда ячейка связна. Раз пути по рёбрам из <tex>s</tex> в <tex>t</tex> нет, то какая-то из них ячеек, пересекаемых отрезком <tex>st</tex>, несвязная. Это возможно, только если какая-то ячейка она представляет собой полосу, ограниченную двумя параллельными прямыми. Но в нашем случае в диаграмме не может быть прямых, пришли к противоречию. [[Файл:voronoi-connected.png|500px]]

=== Линейность Размер структуры ===

|proof=[[Файл:voronoi-infinite-vertex.png|200px|thumb|right]]Для случая сайтов, лежащих на одной прямой, утверждение напрямую следует из вида диаграммы для этого случая, поэтому рассмотрим общий случай. По [[Формула Эйлера|формуле Эйлера ]] <tex>v - e + f = 2</tex>, где <tex>v</tex> — число вершин, <tex>e</tex> — число рёбер и <tex>f</tex> — число граней связного планарного графа. Мы не можем сразу применить эту формулу к <tex>Vor(P)</tex>, потому что в этом графе есть полубесконечные рёбра. Поэтому добавим вершину <tex>n_v_\infty</tex>, и все полубесконечные рёбра мы превратим в рёбра, инцидентные ей. Таким образом мы увеличили число вершин на одну, а число рёбер не изменилось. Число граней равно <tex>n</tex> по определению диаграммы Вороного. Тогда по формуле Эйлера получаем <tex>(v + 1) - e + n = 2</tex>.Сумма степеней всех вершин полученного графа равна <tex>2e</tex>, так как у каждого ребра есть ровно два конца (нет петель). Также у из каждой вершины исходят как минимум три ребра. Отсюда получаем <tex>2e \geqslant 3 (n v + 1)</tex>.

|definition='''Наибольшая пустая окружность ''' точки <tex>q</tex> по отношению к <tex>P</tex> (''largest empty circle of ''<tex>q</tex>'' with respect to ''<tex>P</tex>, <tex>C_P(q)</tex>) — наибольшая окружность с центром в <tex>q</tex> такая, что во внутренности соответствующего ей круга не лежит ни одного сайта из <tex>P</tex>.

|proof=Предположим, что <tex>q</tex> существует, а <tex>p_i, \ p_j, \ p_k</tex> — соответствующие точки. Так как внутри <tex>C_P(q)</tex> нет других сайтов, а <tex>q</tex> равноудалена от точек <tex>p_i, \ p_j, \ p_k</tex>, <tex>q</tex> должна быть на границе <tex>\mathcal{V}(p_i), \ \mathcal{V}(p_j), \ \mathcal{V}(p_k)</tex> одновременно, то есть вершиной диаграммудиаграммы.

|proof=[[Файл:voronoi-circles.png|200px|thumb|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>). Также эта окружность не должна содержать никаких других сайтов внутрина границе, так как тогда она не является вершиной.

|statement=Если соединить все сайты, соответствующие смежным ячейкам диаграммы Вороного, получится [[триангуляция Делоне ]] для этого множества точек.|proof=Если ячейки, соответствующие сайтам <tex>p_i, \ p_j</tex>, смежны, то серединный перпендикуляр к отрезку <tex>p_i p_j</tex> образует ребро диаграммы Вороного, то есть к нему применима предыдущая лемма и можно построить окружность с <tex>p_i</tex> и <tex>p_j</tex> на границе, внутри которой не будет других сайтов. Триангуляции Делоне принадлежат [[Триангуляция Делоне#Критерий Делоне для рёбер|Вспомним]], что триангуляции Делоне принадлежат те и только те ]] рёбра (с поправкой на точки, лежащие на одной окружности), на которых можно построить такую окружность, что внутри неё не будет лежать никаких точек. Тогда ребро <tex>p_i p_j</tex> является ребром триангуляции Делоне. За счёт равносильности в обеих используемых леммах мы добавим все рёбра и не построим лишних.

Будем [[Пересечение полуплоскостей, связь с выпуклыми оболочками|пересекать полуплоскости по ]] по [[#intersect|свойству ячейки диаграммы]]. Необходимо <tex>n</tex> раз для каждого сайта пересечь <tex>n - 1</tex> плоскость, что суммарно делается за <tex>O(n^2 \log n)</tex>.

Храним диаграмму в [[ФайлППЛГ и РСДС (PSLG и DCEL):voronoi-incremental.pngопределение, построение РСДС множества прямых|200px|thumb|rightРСДС]]Храним диаграмму в РСДС. Пусть у нас уже есть диаграмма для точек <tex>p_1, p_2, ..., p_i</tex>. Добавим новый сайт <tex>p_{i+1}</tex>. Сначала найдём сайт <tex>p_j</tex>, в ячейку которого попадает <tex>p_{i+1}</tex>, перебором. После этого строим новую ячейку: сначала проведём серединный перпендикуляр для <tex>p_{i+1}p_j</tex>, он пересечёт границу ячейки <tex>\mathcal{V}(p_j)</tex> с ячейкой <tex>\mathcal{V}(p_k)</tex>; на следующем шаге будем строить серединный перпендикуляр для <tex>p_{i+1} p_k</tex> и так далее. В процессе построения перпендикуляров необходимо обновлять РСДС. Каждый раз, когда новое полуребро <tex>e</tex>, порождаемое <tex>p_{i+1}</tex> и <tex>p_j</tex>, пересекает существовавшее ранее полуребро <tex>e'</tex>, создаётся новая вершина <tex>v</tex> и начинается новое полуребро <tex>e+1</tex>.

[[ФайлОбновление РСДС происходит следующим образом:voronoi-update-dcel.png|400px|thumb|left]]В процессе построения перпендикуляров необходимо обновлять РСДС. Каждый раз, когда новое ребро <tex>e</tex>, порождаемое <tex>p_{i+1}</tex> и <tex>p_j</tex>, пересекает существовавшее ранее ребро <tex>e'</tex>, создаётся новая вершина <tex>v</tex> и начинается новое ребро <tex>e+1</tex>.

* создаём вершину <tex>v</tex> с полуребром <tex>e</tex>;* для ребра полуребра <tex>e</tex> в РСДС второй конец в вершине <tex>v</tex>, следующее ребро полуребро — <tex>e'</tex>, инцидентные грани — слева <tex>\mathcal{V}(i+1)</tex>, справа — <tex>\mathcal{V}(j)</tex>;* добавляем в РСДС ребро полуребро <tex>e + 1</tex> с началом в <tex>v</tex> и предыдущим ребром полуребром <tex>e</tex>;* удаляем все рёбраполурёбра, лежащие между вершиной начала <tex>e</tex> и вершиной конца <tex>e</tex>, по часовой стрелке;* обновляем реброполуребро, соответствующее грани для <tex>\mathcal{V}(p_j)</tex> — им становится <tex>e</tex>;* создаём вершину <tex>v</tex> с ребром <tex>e</tex>.

{||[[Файл:voronoi-incremental-zero-step.png|200px|thumb|Локализация]]|[[Файл:voronoi-incremental-first-step.png|200px|thumb|Добавление первого ребра]]|[[Файл:voronoi-incremental.png|200px|thumb|Добавление третьего ребра]]|[[Файл:voronoi-update-dcel.png|400px|thumb|Обновление структуры при добавлении ребра]]|} === Диаграмма <tex>k</tex>-го порядка Алгоритм Форчуна ===Ячейка Вороного <tex>k</tex>Построение производится при помощи заметающей прямой и парабол позади неё (параболы в данном случае -го порядка — множество это множества точек, имеющих равноудалённых от вершины и прямой). Сама диаграмма "рисуется" местами соприкасания соседних парабол. Несмотря на то, что в качестве ближайших теории движение прямой происходит непрерывно, сам алгоритм обрабатывает только крайние случаи, когда происходят события. Рассматривается 2 типа событий - появление новой параболы, когда заметающая прямая касается вершины, и схлопывание параболы - когда две соседние параболы её полностью накрывают. Всего событий <tex>kO(n)</tex> соседей определённое множество из (<tex>kn</tex> сайтов- число вершин). Чтобы построить диаграмму Для каждого события вычисляется его время (позиция заметающей прямой), события кладутся в очередь с приоритетом (отсюда <tex>kO(\log n)</tex>-го порядкапо времени) и обрабатываются, пока очередь непуста. При обработке событий также записываются пары взаимодействующих вершин (у которых сайты имеют общую границу), нужно взять диаграмму <tex>k - 1</tex>-го порядка для первых <tex>k - 1</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|выпуклая оболочка]]. Поскольку параболоид выпуклый, никакие вершины не будут удалены. На выходе получаются рёбра между вершинами, которые соответствуют триангуляции Делоне. Сложность работы - 1<tex>O(n \log n)</tex>. == Диаграмма k-го порядка является farthest=={{Определение|definition='''Ячейка Вороного''' <tex>k</tex>'''-point диаграммойго порядка''' (<tex>\mathcal{V}_k(p_1, p_2, т.е. ., p_k)</tex>) — множество точек, имеющих в каждой её ячейке все качестве ближайших <tex>k</tex> соседей множество сайтов <tex>p_1, p_2, ..., p_k</tex>.}} Чтобы построить диаграмму <tex>k</tex>-го порядка, возьмём диаграмму <tex>k - 1</tex>-го порядка. Каждая ячейка построена для некоторого набора <tex>k-1</tex> сайтов. Обозначим множество этих сайтов за <tex>S</tex>. [[Пересечение выпуклых многоугольников|Пересечём]] каждую из этих ячеек с ячейками диаграммы первого порядка, построенной на множестве сайтов <tex>P \setminus S</tex>. Когда мы пересекаем ячейку <tex>k-1</tex>-го порядка для точек <tex>S</tex> с ячейкой первого порядка для точки являются наиболее удалёнными от какого-то сайта<tex>p_i</tex>, получаем ячейку для множества <tex>S \cup \{p_i\}</tex>. После пересечения ячеек необходимо объединить те, которые отвечают за одинаковый набор сайтов (это могут быть только соседние по ребру ячейки). Итого совершаем <tex>k</tex> шагов, на каждом строим <tex>O(n)</tex> диграмм Вороного за время <tex>O(n^3)</tex>, пересекаем <tex>O(n)</tex> ячеек с <tex>O(n)</tex> ячейками за <tex>O(n)</tex> времени, а потом объединяем ячейки за <tex>O(n)</tex> (линейное количество соседних рёбер ячейки, а объединение происходит за <tex>O(1)</tex> за счёт структуры РСДС). Итого <tex>O(k \cdot n^3)</tex>.

|[[Файл:voronoi-tenth-order.png|200px|thumb|Диаграмма десятого <tex>n - 1</tex>-го порядка, (она же farthest-pointдиаграмма) для данного набора сайтов]]

=== Алгоритм ===Чтобы найти farthest-point диаграмму, сначала найдём выпуклую оболочку всех сайтов. Обозначим сайты, её образующие, через <tex>p_1, p_2, ..., p_m</tex>. Делаем их случайную перестановку, но запомним Запомним порядки обхода в для каждой вершины выпуклой оболочке оболочки по часовой стрелке (<tex>cw(p_i)</tex>) и против часовой (<tex>ccw(p_i)</tex>)и сделаем случайную перестановку точек. Далее удаляем из выпуклой оболочки все точки, кроме первых трёх (запоминая при этом их соседей в оболочке на момент удаления). После этого мы строим farthest-point диаграмму для первых трёх точек (пересекая полуплоскости) и последовательно добавляем остальные (удалённые) в порядке, обратном порядку удаления.

|[[Файл:voronoi-farthest-construct.png|600px|thumb|Построение очередной ячейки farthest-point диаграммы]]

* [http://students.info.uaic.ro/~emilian.necula/vor2.pdf Инкрементальный алгоритмAlgorithms for constructing Voronoi diagrams, Vera Sacrist´an {{---}} Incremental algorithm]

* [https://web.archive.org/web/20170329014016/http://www.cs.uu.nl/docs/vakken/ga/slides7b.pdf Диаграммы высших порядковComputational Geometry {{---}} Lecture 13: More on Voronoi diagrams]