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

Эта статья находится в разработке!

Определения

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

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

Есть множество точек [math]P[/math] на плоскости. Для всех точек [math]q \notin P[/math] этой плоскости узнаем ближайшую к [math]q[/math] точку из [math]P[/math]. Таким образом получим разбиение плоскости на кусочки, в каждом из которых содержится одна точка [math]p_i[/math] из [math]P[/math] и все точки [math]q[/math], для которых [math]p_i[/math] — ближайшая среди точек из [math]P[/math].

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

[math]P = \{ p_1, p_2, ..., p_n\}[/math] — множество точек на плоскости. Назовём их сайтами (site).

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

Диаграмма Вороного (Voronoi diagram, [math]Vor(P)[/math]) для сайтов [math]P = \{ p_1, p_2, ..., p_n\}[/math] на плоскости — это разбиение плоскости на [math]n[/math] ячеек (ячейка Вороного, Voronoi cell, [math]\mathcal{V}(p_i)[/math]), по одной для каждого сайта, которые обладают свойством: [math]\rho(q, p_i) \lt \rho(q, p_j)[/math] для всех [math]p_j \in P, \ j \neq i[/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 \in h(p, q)[/math] тогда и только тогда, когда [math]\rho(r, p) \lt \rho(r, q)[/math]. Отсюда вытекает следующее:

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

[math]\mathcal{V}(p_i) = \cap_{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]\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]n_\infty[/math], и все полубесконечные рёбра мы превратим в рёбра, инцидентные ей. Таким образом мы увеличили число вершин на одну, а число рёбер не изменилось. Число граней равно [math]n[/math] по определению диаграммы Вороного. Тогда по формуле Эйлера получаем [math](v + 1) - e + n = 2[/math]. Сумма степеней всех вершин полученного графа равна [math]2e[/math], так как у каждого ребра есть ровно два конца (нет петель). Также у из каждой вершины исходят как минимум три ребра. Отсюда получаем [math]2e \geqslant 3 (n + 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] ([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]\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]\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[/math] раз пересечь [math]n - 1[/math] плоскость, что суммарно делается за [math]O(n^2 \log n)[/math].