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

Определения

Совсем неформальное определение

Пример диаграммы Вороного

Пусть есть карта города, на которой точками обозначены почтовые отделения. Человек хочет отправить письмо, и он пойдёт на ближайшую почту. Ему интересно знать, какое отделение ближе, для любой точки города — необходимость отправить письмо может наступить неожиданно. Для этого он может взять карту и расчертить её на ячейки так, чтобы внутри каждой ячейки находилось только одно отделение, а для всех остальных точек ячейки именно эта почта была ближайшей. Полученная картинка и будет диаграммой Вороного для точек-почт.

Неформальное определение

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

Формальное определение

[math]P = \{ p_1, p_2, ..., p_n\}[/math] — множество точек на плоскости.

Определение:

[math]p_i \in P[/math] называется сайтом (site).

Определение:

Ячейка Вороного (Voronoi cell, [math]\mathcal{V}(p_i)[/math]) — множество точек плоскости [math]q[/math] таких, что для фиксированного сайта [math]p_i[/math] и любых других сайтов [math]p_j \in P, \ j \neq i[/math] верно неравенство [math]\rho(q, p_i) \lt \rho(q, p_j)[/math].

Определение:

Диаграмма Вороного (Voronoi diagram, [math]Vor(P)[/math]) для сайтов [math]P = \{ p_1, p_2, ..., p_n\}[/math] на плоскости — это разбиение плоскости на ячейки Вороного для каждого сайта из [math]P[/math].

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

Свойства

Связь с пересечением полуплоскостей

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

Утверждение:

[math]\mathcal{V}(p_i) = \bigcap\limits_{1 \leqslant j \leqslant n, j \neq i} h(p_i, p_j)[/math]

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

Топология диаграммы Вороного

Теорема:

Пусть [math]P[/math] — множество из [math]n[/math] сайтов. Если они все лежат на одной прямой, то [math]Vor(P)[/math] представляет собой [math]n - 1[/math] параллельную прямую. Иначе [math]Vor(P)[/math] связная и все её рёбра — либо отрезки, либо лучи.

Доказательство:

[math]\triangleright[/math]

В случае, если все сайты лежат на одной прямой, каждая пара соседних сайтов порождает серединный перпендикуляр к отрезку, содержащему их, и, соответственно, к прямой, которая содержит все сайты. Так получаются [math]n - 1[/math] прямая, каждая из которых перпендикулярна прямой, содержащей сайты, а значит, эти прямые параллельны. Рассмотрим теперь случай, когда сайты не лежат на одной прямой. Покажем, что рёбра — это отрезки или лучи, от противного. Предположим, что есть ребро [math]e[/math], являющееся прямой. Пусть оно — граница ячеек [math]\mathcal{V}(p_i)[/math] и [math]\mathcal{V}(p_j)[/math]. Пусть точка [math]p_k \in P[/math] не лежит на прямой [math]p_i p_j[/math] (по условию такая точка существует). Тогда серединный перпендикуляр к [math]p_j p_k[/math] не параллелен [math]e[/math], и, значит, он его пересекает. Но тогда та часть [math]e[/math], что лежит в [math]h(p_k, p_j)[/math], не может быть границей [math]\mathcal{V}(p_j)[/math], потому что она ближе к [math]p_k[/math], чем к [math]p_j[/math]. Пришли к противоречию. Докажем теперь, что диаграмма связна. Предположим, что это не так. Тогда на её рёбрах найдутся две точки [math]s[/math] и [math]t[/math], между которыми нет пути по рёбрам диаграммы. Рассмотрим отрезок [math]st[/math]. Он пересекает некоторое количество ячеек диаграммы. Пусть он пересекает какую-то ячейку в точках [math]a[/math] и [math]b[/math]. От точки [math]a[/math] до точки [math]b[/math] можно добраться по рёбрам тогда и только тогда, когда ячейка связна. Раз пути из [math]s[/math] в [math]t[/math] нет, то какая-то из ячеек, пересекаемых отрезком [math]st[/math], несвязная. Это возможно, только если она представляет собой полосу, ограниченную двумя параллельными прямыми. Но в нашем случае в диаграмме не может быть прямых, пришли к противоречию.

[math]\triangleleft[/math]

Размер структуры

Теорема:

Для [math]n \geqslant 3[/math] сайтов диаграмма Вороного содержит не больше [math]2n - 5[/math] вершин и [math] 3n - 6[/math] рёбер.

Доказательство:

[math]\triangleright[/math]

Для случая сайтов, лежащих на одной прямой, утверждение напрямую следует из вида диаграммы для этого случая, поэтому рассмотрим общий случай. По формуле Эйлера [math]v - e + f = 2[/math], где [math]v[/math] — число вершин, [math]e[/math] — число рёбер и [math]f[/math] — число граней связного планарного графа. Мы не можем сразу применить эту формулу к [math]Vor(P)[/math], потому что в этом графе есть полубесконечные рёбра. Поэтому добавим вершину [math]v_\infty[/math], и все полубесконечные рёбра мы превратим в рёбра, инцидентные ей. Таким образом мы увеличили число вершин на одну, а число рёбер не изменилось. Число граней равно [math]n[/math] по определению диаграммы Вороного. Тогда по формуле Эйлера получаем [math](v + 1) - e + n = 2[/math]. Сумма степеней всех вершин полученного графа равна [math]2e[/math], так как у каждого ребра есть ровно два конца (нет петель). Также из каждой вершины исходят как минимум три ребра. Отсюда получаем [math]2e \geqslant 3 (v + 1)[/math]. Домножим равенство на два и вычтем из него полученную нижнюю границу для [math]2 \cdot e[/math], в результате получим [math] v \leqslant 2n - 5[/math]. Далее подставим этот результат в равенство и получим [math]e \leqslant 3n - 6[/math], что и требовалось доказать.

[math]\triangleleft[/math]

Связь с триангуляцией Делоне

Определение:

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

Лемма:

Точка [math]q[/math] — вершина диаграммы Вороного в том и только в том случае, когда [math]C_P(q)[/math] содержит три и более сайтов на своей границе.

Доказательство:

[math]\triangleright[/math]

Предположим, что [math]q[/math] существует, а [math]p_i, \ p_j, \ p_k[/math] — соответствующие точки. Так как внутри [math]C_P(q)[/math] нет других сайтов, а [math]q[/math] равноудалена от точек [math]p_i, \ p_j, \ p_k[/math], [math]q[/math] должна быть на границе [math]\mathcal{V}(p_i), \ \mathcal{V}(p_j), \ \mathcal{V}(p_k)[/math] одновременно, то есть вершиной диаграммы. Докажем в другую сторону: каждая вершина [math]q[/math] диаграммы инцидентна минимум трём рёбрам, и, поэтому, как минимум трём ячейкам [math]\mathcal{V}(p_i), \ \mathcal{V}(p_j), \ \mathcal{V}(p_k)[/math]. Тогда [math]q[/math] лежит на равном расстоянии от [math]p_i, \ p_j, \ p_k[/math] и не может быть другого сайта ближе к [math]q[/math], так как иначе [math]\mathcal{V}(p_i), \ \mathcal{V}(p_j), \ \mathcal{V}(p_k)[/math] не сойдутся в [math]q[/math]. Поэтому можно построить окружность с центром в [math]q[/math] и [math]p_i, \ p_j, \ p_k[/math] на границе так, что внутри не будет других сайтов.

[math]\triangleleft[/math]

Лемма:

Серединный перпендикуляр к отрезку [math]p_i p_j[/math] образует ребро диаграммы Вороного в том и только в том случае, если на нём есть точка [math]q[/math] такая, что [math]C_P(q)[/math] содержит на своей границе только сайты [math]p_i, \ p_j[/math].

Доказательство:

[math]\triangleright[/math]

Предположим, что [math]q[/math] существует. Тогда, так как [math]C_P(q)[/math] не содержит в себе сайтов и содержит [math]p_i, \ p_j[/math] на границе, [math] \rho(q, p_i) = \rho(q, p_j) \leqslant \rho(q, p_k), \ 1 \leqslant k \leqslant n[/math]. Отсюда выходит, что [math]q[/math] — вершина [math]Vor(P)[/math] или лежит на ребре диаграммы. Но по предыдущей лемме выходит, что [math]q[/math] не может быть вершиной диаграммы. Значит, она лежит на ребре, заданном серединным перпендикуляром к [math]p_i p_j[/math]. Докажем в другую сторону: пусть серединный перпендикуляр к [math]p_i p_j[/math] задаёт ребро диаграммы. Наибольшая пустая окружность любой точки [math]q[/math] на этом ребре должна содержать на границе [math]p_i[/math] и [math]p_j[/math] (так как [math]q[/math] равноудалена от [math]p_i[/math] и [math]p_j[/math]). Также эта окружность не должна содержать никаких других сайтов на границе, так как тогда она не является вершиной.

[math]\triangleleft[/math]

Теорема:

Если соединить все сайты, соответствующие смежным ячейкам диаграммы Вороного, получится триангуляция Делоне для этого множества точек.

Доказательство:

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

Построение

Наивный алгоритм

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

Инкрементальный алгоритм

Храним диаграмму в РСДС. Пусть у нас уже есть диаграмма для точек [math]p_1, p_2, ..., p_i[/math]. Добавим новый сайт [math]p_{i+1}[/math]. Сначала найдём сайт [math]p_j[/math], в ячейку которого попадает [math]p_{i+1}[/math], перебором. После этого строим новую ячейку: сначала проведём серединный перпендикуляр для [math]p_{i+1}p_j[/math], он пересечёт границу ячейки [math]\mathcal{V}(p_j)[/math] с ячейкой [math]\mathcal{V}(p_k)[/math]; на следующем шаге будем строить серединный перпендикуляр для [math]p_{i+1} p_k[/math] и так далее.

В процессе построения перпендикуляров необходимо обновлять РСДС. Каждый раз, когда новое полуребро [math]e[/math], порождаемое [math]p_{i+1}[/math] и [math]p_j[/math], пересекает существовавшее ранее полуребро [math]e'[/math], создаётся новая вершина [math]v[/math] и начинается новое полуребро [math]e+1[/math].

Обновление РСДС происходит следующим образом:

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

Каждый шаг выполняется за [math]O(i)[/math], значит, суммарно диаграмма из [math]n[/math] сайтов с нуля создаётся за [math]O(n^2)[/math].

Локализация

Добавление первого ребра

Добавление третьего ребра

Обновление структуры при добавлении ребра

Алгоритм Форчуна

Построение производится при помощи заметающей прямой и парабол позади неё (параболы в данном случае - это множества точек, равноудалённых от вершины и прямой). Сама диаграмма "рисуется" местами соприкасания соседних парабол. Несмотря на то, что в теории движение прямой происходит непрерывно, сам алгоритм обрабатывает только крайние случаи, когда происходят события. Рассматривается 2 типа событий - появление новой параболы, когда заметающая прямая касается вершины, и схлопывание параболы - когда две соседние параболы её полностью накрывают. Всего событий [math]O(n)[/math] ([math]n[/math] - число вершин). Для каждого события вычисляется его время (позиция заметающей прямой), события кладутся в очередь с приоритетом (отсюда [math]O(\log n)[/math] по времени) и обрабатываются, пока очередь непуста. При обработке событий также записываются пары взаимодействующих вершин (у которых сайты имеют общую границу), это и является результатом работы алгоритма.

Сложность работы алгоритма - [math]O(n \log n)[/math] по времени и [math]O(n)[/math] по памяти.

Более подробно:

• Описание алгоритма на Wikipedia
• Презентация с описанием в деталях

Алгоритм Чана

Вершины проецируются из двумерной плоскости на поверхность параболоида ([math]x, y[/math] остаются те же, добавляется [math]z = x^2 + y^2[/math]). Далее по ним строится нижняя выпуклая оболочка. Поскольку параболоид выпуклый, никакие вершины не будут удалены. На выходе получаются рёбра между вершинами, которые соответствуют триангуляции Делоне. Сложность работы - [math]O(n \log n)[/math].

Диаграмма k-го порядка

Определение:

Ячейка Вороного [math]k[/math]-го порядка ([math]\mathcal{V}_k(p_1, p_2, ..., p_k)[/math]) — множество точек, имеющих в качестве ближайших [math]k[/math] соседей множество сайтов [math]p_1, p_2, ..., p_k[/math].

Чтобы построить диаграмму [math]k[/math]-го порядка, возьмём диаграмму [math]k - 1[/math]-го порядка. Каждая ячейка построена для некоторого набора [math]k-1[/math] сайтов. Обозначим множество этих сайтов за [math]S[/math]. Пересечём каждую из этих ячеек с ячейками диаграммы первого порядка, построенной на множестве сайтов [math]P \setminus S[/math]. Когда мы пересекаем ячейку [math]k-1[/math]-го порядка для точек [math]S[/math] с ячейкой первого порядка для точки [math]p_i[/math], получаем ячейку для множества [math]S \cup \{p_i\}[/math]. После пересечения ячеек необходимо объединить те, которые отвечают за одинаковый набор сайтов (это могут быть только соседние по ребру ячейки).

Итого совершаем [math]k[/math] шагов, на каждом строим [math]O(n)[/math] диграмм Вороного за время [math]O(n^3)[/math], пересекаем [math]O(n)[/math] ячеек с [math]O(n)[/math] ячейками за [math]O(n)[/math] времени, а потом объединяем ячейки за [math]O(n)[/math] (линейное количество соседних рёбер ячейки, а объединение происходит за [math]O(1)[/math] за счёт структуры РСДС). Итого [math]O(k \cdot n^3)[/math].

Диаграмма первого порядка

Диаграмма второго порядка

Диаграмма третьего порядка

Диаграмма [math]n - 1[/math]-го порядка (она же farthest-point диаграмма) для данного набора сайтов

Farthest-point диаграмма

Определение:

Диаграмма [math]n - 1[/math]-го порядка является farthest-point диаграммой, т.е. в каждой её ячейке все точки являются наиболее удалёнными от какого-то сайта.

Свойства

Лемма:

Для любой точки [math]q[/math] плоскости самый удалённый от неё сайт из [math]P[/math] должен лежать на выпуклой оболочке [math]P[/math].

Доказательство:

[math]\triangleright[/math]

Сайт, не находящийся на выпуклой оболочке, лежит внутри неё по свойствам выпуклой оболочки. Пусть самый удалённый от точки [math]q[/math] сайт [math]p_i[/math] не лежит на выпуклой оболочке (т.е. лежит внутри неё). Проведём луч [math]q p_i[/math]. Он пересечёт ребро выпуклой оболочки [math]p_j p_k[/math]. Получатся два смежных угла, рассмотрим тот, который оказался прямым или тупым. Тогда в полученном треугольнике [math]\rho(q, p_j) \gt \rho(q, p_i)[/math], так как напротив большего угла лежит большая сторона. Пришли к противоречию.

[math]\triangleleft[/math]

Лемма:

Сайт, который лежит внутри выпуклой оболочки сайтов, не может иметь ячейку в farthest-point диаграмме.

Доказательство:

[math]\triangleright[/math]

Пусть это не так и сайт [math]p[/math] лежит внутри выпуклой оболочки и имеет ячейку в farthest-point диаграмме. Тогда внутри неё есть точка [math]q[/math]. Но по предыдущей лемме самый удалённый для [math]q[/math] сайт лежит на выпуклой оболочке, а значит, сайт [math]p[/math] не может быть самым удалённым для [math]q[/math]. Пришли к противоречию.

[math]\triangleleft[/math]

Лемма:

Каждый сайт, который является вершиной выпуклой оболочки сайтов, имеет ячейку в farthest-point диаграмме.

Доказательство:

[math]\triangleright[/math]

Докажем по индукции. База индукции: для двух сайтов они оба являются вершинами выпуклой оболочки и оба имеют ячейку в farthest-point диаграмме (дальняя от сайта полуплоскость). Переход: добавим сайт [math]p[/math] так, что он станет новой вершиной выпуклой оболочки. Пусть он не имеет ячейку в farthest-point диаграмме, то есть уже имеющаяся перед его добавлением диаграмма не меняется. Для построения farthest-point диаграммы проводятся серединные перпендикуляры между всеми парами сайтов, и полученные полуплоскости пересекаются; раз новой ячейки не добавилось, то серединные перпендикуляры между [math]p[/math] и остальными сайтами совпали с уже имеющимися перпендикулярами. Это возможно, только если [math]p[/math] совпал с другим сайтом. Пришли к противоречию.

[math]\triangleleft[/math]

Утверждение:

Сайт имеет ячейку в farthest-point диаграмме тогда и только тогда, когда он является вершиной выпуклой оболочки всех сайтов.

[math]\triangleright[/math]

Непосредственно следует из двух предыдущих лемм.

[math]\triangleleft[/math]

Утверждение:

Все ячейки в farthest-point диаграмме неограничены.

[math]\triangleright[/math]

Пусть [math]p_i[/math] — сайт на выпуклой оболочке сайтов, а [math]q[/math] — точка, для которой он является наиболее удалённым. Тогда для всех точек на луче, лежащем на [math]p_i q[/math], начинающемся в [math]q[/math] и не проходящим через [math]p_i[/math], сайт [math]p_i[/math] будет наиболее удалённым среди остальных сайтов. Значит, ячейка сайта [math]p_i[/math] в farthest-point диаграмме включает в себя этот луч, а значит, неограничена.

[math]\triangleleft[/math]

Алгоритм

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

Построение очередной ячейки farthest-point диаграммы

Для точки [math]p_i[/math] ячейка встанет «между» ячейками, соответствующими [math]cw(p_i)[/math] и [math]ccw(p_i)[/math]. Перед добавлением [math]p_i[/math] [math]cw(p_i)[/math] и [math]ccw(p_i)[/math] — соседи, поэтому между ними построен серединный перпендикуляр. Серединный перпендикуляр к [math]p_i ccw(p_i)[/math] даст новое ребро, которое лежит в farthest-point ячейке [math]ccw(p_i)[/math] и является частью границы ячейки [math] p_i[/math]. Обойдём ячейку [math]ccw(p_i)[/math] по часовой стрелке, чтоб понять, какое ребро пересечёт перпендикуляр. С другой стороны этого ребра лежит ячейка какой-то точки [math]p_j[/math], и серединный перпендикуляр [math]p_i p_j[/math] тоже даст ребро ячейке [math]p_i[/math]. Аналогично совершим обход и так далее. Последний серединный перпендикуляр будет построен для [math]p_i cw(p_i)[/math]. После этого удаляем рёбра, которые лежат внутри новой ячейки.

См. также

• Трапецоидная карта
• Триангуляция Делоне
• Straight skeleton

Источники

• de Berg, Cheong, van Kreveld, Overmars. Computational Geometry, Algorithms and Applicants, 2008. pp. 147-151, 164-166
• Algorithms for constructing Voronoi diagrams, Vera Sacrist´an — Incremental algorithm
• Wikipedia — Voronoi diagram
• Computational Geometry — Lecture 13: More on Voronoi diagrams