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

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

Определения

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

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

Есть множество точек [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].

Обозначения и определения

Сайт (site) — общее название для точки [math]p[/math] или замкнутого отрезка [math]t[/math].

[math]t^\circ[/math] — внутренняя часть отрезка. Внутренность точки — пустое множество.

Два замкнутых пересекающихся сайта слабо пересекаются (weakly intersect), если точка их пересечения не принадлежит их внутренностям, то есть они касаются концами.

Два сайта сильно пересекаются (strongly intersect), если точка их пересечения принадлежит внутренности хотя бы одного из данных сайтов.

Расстояние от точки [math]x \in \mathbb{E}^2[/math] до замкнутого сайта [math]S_i[/math]: [math]\delta(x, S_i) = \min{\{||x - y|| : y \in S_i\}}[/math].

Пусть [math]H_{ij} = \{x \in \mathbb{E}^2 : \delta(x, S_i) \le \delta(x, S_j)\}[/math]. Ячейка Вороного (Voronoi cell) [math]V(S_i, \Sigma)[/math] — множество точек, которые находятся ближе к [math]S_i[/math], чем к любому другому сайту, то есть [math]V(S_i, \Sigma) = \cap_{i \ne j}H_{ij}[/math].

Ребро Вороного (Voronoi edge) — связное множество точек, принадлежащих пересечению ровно двух ячеек Вороного.

Вершина Вороного (Voronoi vertex) — точка, которая принадлежит хотя бы трём ячейкам Вороного.

Диаграмма Вороного (Voronoi diagram) [math]V(\Sigma)[/math] множества сайтов [math]\Sigma[/math] — разбиение плоскости на вершины, рёбра и ячейки Вороного.

1-каркас (1-skeleton) [math]V_1(\Sigma)[/math] — набор вершин и рёбер Вороного.

В процессе работы алгоритма множество сайтов, которые подаются на вход, может измениться. Чтобы различать начальное и конечное множество сайтов, будем обозначать входное множество через [math]\Sigma_I[/math], а множество сайтов, которые присутствуют на результирующей диаграмме Вороного, через [math]\Sigma[/math]. [math]\Sigma_I[/math] всегда состоит из замкнутых сайтов, а [math]\Sigma[/math] — из точек и открытых отрезков.

Пусть сайты [math]S_i[/math] и [math]S_j[/math] слабо пересекаются. Тогда битангентная окружность Вороного (bitangent Voronoi circle) [math]C_{ij}[/math] — окружность, касающаяся одновременно [math]S_i[/math] и [math]S_j[/math]. При рассмотрении трёх сайтов [math]S_i[/math], [math]S_j[/math] и [math]S_k[/math], окружность, касающаяся всех трёх сайтов, называется тритангентной окружностью Вороного (tritangent Voronoi circle). Точки, принадлежащие рёбрам Вороного, являются центрами битангентных окружностей, а вершины — тритангентных.

Рассмотрим [math]S \notin \Sigma_I[/math]. Будем говорить, что [math]S[/math] конфликтует с окружностью Вороного [math]C[/math], если [math]S[/math] пересекается с кругом, ограниченным [math]C[/math]. Также [math]S[/math] конфликтует с ребром [math]e \in V(S, \Sigma)[/math], если он пересекается с кругом, ограниченным одной из окружностей Вороного с центром в точке, принадлежащей [math]e[/math]. Область конфликтов (conflict region) [math]R_\Sigma(S)[/math] — множество точек 1-каркаса [math]V_1(\Sigma)[/math], соответствующих окружностям Вороного, которые конфликтуют с [math]S[/math].

Алгоритм

Рассмотрим сначала алгоритм для слабо пересекающихся сайтов, а потом обобщим его для случая сильно пересекающихся сайтов.

Случай слабо пересекающихся сайтов

Пусть мы уже построили диаграмму Вороного для некоторого множества [math]\Sigma[/math]. Рассмотрим процедуру вставки нового сайта [math]S[/math].

Алгоритм состоит из четырёх шагов:

1. Найти первый конфликт сайта [math]S[/math] с каркасом [math]V_1(\Sigma)[/math].

2. Найти всю область конфликтов сайта [math]S[/math] c каркасом [math]V_1(\Sigma)[/math].

3. Построить диаграмму Вороного для [math]\Sigma \cup \{S\} [/math].

4. Обновить локализационную структуру.

Лемма:

[math]\Sigma[/math] — слабо пересекающееся между собой множество сайтов. Тогда [math]\forall s \in \Sigma[/math] ячейки Вороного [math]V(s, \Sigma)[/math] — односвязные множества.

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

[math]\triangleright[/math]

Для начала докажем, что ячейки связны. Пусть это не так и у ячейки [math]V(s, \Sigma)[/math] несколько компонент связности. Рассмотрим [math]\varepsilon[/math] — одну из тех, которая не содержит в себе [math]s[/math]. Начнём идти по кратчайшему пути [math]P[/math] от любой точки [math]p \in \varepsilon[/math] до [math]s[/math]. Так как [math]p[/math] и [math]s[/math] лежат в разных компонентах связности, найдётся [math]s' \in \Sigma[/math], такой что путь [math]P[/math] проходит через [math]V(s', \Sigma)[/math]. Значит существует путь от [math]p[/math] до [math]s'[/math], который короче, чем [math]P[/math], следовательно и [math]\delta(p, s') \lt \delta(p, s) = |P|[/math]. Противоречие. Теперь допустим, что [math]V(s, \Sigma)[/math] содержит разрыв в виде другой ячейки [math]V(s', \Sigma)[/math]. Проведём прямую, которая соответствует кратчайшему расстоянию между [math]s[/math] и [math]s'[/math] и рассмотрим точку [math]p[/math], которая лежит на её продолжении за [math]s'[/math] и принадлежит [math]V(s, \Sigma)[/math]. Такая точка будет существовать, т.к. [math]V(s', \Sigma)[/math] лежит внутри [math]V(s, \Sigma)[/math]. Получаем, что кратчайший путь от [math]p[/math] до [math]s[/math] проходит через [math]s'[/math]. Опять противоречие.

[math]\triangleleft[/math]

Теорема: Пусть [math]\Sigma[/math] — множество слабо пересекающихся сайтов, [math]s[/math] — сайт, [math]s \notin \Sigma[/math]. Тогда [math]R_\Sigma(s)[/math] — связное непустое множество. Доказательство: [math]\triangleright[/math] Пусть [math]C = V(s, \Sigma \cup \{s\})[/math], [math]R_\Sigma(s) = \varepsilon[/math]. Заметим, что [math]\varepsilon = V_1(\Sigma) \cap C[/math]. Если бы область конфликтов [math]\varepsilon[/math] была пустой, то было бы верно [math]C \subset V(q, \Sigma \cup \{p\})[/math] для некоторого [math]q \in \Sigma[/math] и [math]V(q, \Sigma \cup s)[/math] не было бы односвязным. Пусть [math]\varepsilon_1, \varepsilon_2, ... , \varepsilon_k[/math] — связные компоненты [math]\varepsilon[/math] для некоторого [math]k[/math]. Предположим, что [math]k \ge 2[/math]. Тогда cуществует путь [math]P \subseteq C \setminus \varepsilon[/math], соединяющий две точки [math]x[/math] и [math]y[/math] на границе [math]C[/math] и отделяющий [math]\varepsilon_1[/math] от [math]\varepsilon_2[/math](см. рисунок). [math]P \cap \varepsilon = \varnothing \Rightarrow P \cap V_1(\Sigma) = \varnothing \Rightarrow P \subseteq intV(q, \Sigma)[/math] для некоторого [math]q \in \Sigma[/math]. [math]x, y \in P \Rightarrow[/math] все достаточно малые окрестности [math]U(x)[/math], [math]U(y)[/math] полностью содержатся в [math]V(q, \Sigma)[/math]. Значит, точки пересечения этих окрестностей с дополнением [math]C[/math] лежат в [math]V(q, \Sigma \cup s)[/math] и могут быть соединены путём [math]L \subseteq V(q, \Sigma \cup \{s\}) \subseteq V(q, \Sigma)[/math]. Следовательно, цикл [math]P \circ L[/math] полностью содержится в [math]V(q, \Sigma)[/math] и содержит [math]\varepsilon_1[/math] или [math]\varepsilon_2[/math] в своей внутренней части. Это противоречит тому, что [math]V(q, \Sigma)[/math] — односвязное множество, следовательно [math]k = 1[/math]. [math]\triangleleft[/math]

Таким образом, для нахождения области конфликтов, можно найти одно конфликтующее ребро, а затем, при помощи DFS, найти все остальные.

Пусть сайт [math]S[/math] — это точка [math]p[/math].

Первый шаг алгоритма начинается с поиска ближайшего соседа [math]N_\Sigma(p)[/math] точки p среди сайтов [math]\Sigma[/math] (если есть несколько ближайших, то подойдёт любой из них). Будем хранить нашу диаграмму в скип-листе для того, чтобы можно было быстро выполнять эти запросы. Либо [math]N_\Sigma(p)[/math] и [math]p[/math] — это одна и та же точка, и ничего делать не нужно, либо [math]p[/math] конфликтует хотя бы с одним ребром, принадлежащим границе ячейки [math]V(N_\Sigma(p))[/math]. Тогда первый шаг завершается рассмотрением границы [math]V(N_\Sigma(p))[/math] и возвращением одного из рёбер, конфликтующих с [math]p[/math]. Как было сказано раньше, второй шаг — DFS по рёбрам [math]V_1(\Sigma)[/math] с целью найти все рёбра, конфликтующие с точкой [math]p[/math]. Теперь, зная [math]R_\Sigma(p)[/math], можно создать новую ячейку Вороного [math]V(S, \Sigma \cup \{S\})[/math] (а как это сделать, я не очень понимаю).

Если же [math]S[/math] — это замкнутый отрезок [math]t[/math], то сначала вставляем конечные точки [math]p'_t[/math] и [math]p''_t[/math], используя процедуру, описанную выше. Остаётся вставить открытый отрезок [math]t^\circ[/math]. Так как [math]p'_t[/math] и [math]p''_t[/math] — соседи [math]t^\circ[/math] в диаграмме [math]V(\Sigma \cup \{p'_t, p''_t, t^\circ\})[/math], [math]t^\circ[/math] обязан конфликтовать с каким-нибудь ребром ячейки, соответствующей [math]p'_t[/math] или [math]p''_t[/math]. Таким образом, первый конфликт [math]t^\circ[/math] с [math]V_1(\Sigma \cup \{p'_t, p''_t\})[/math] можно найти, просматривая рёбра ячейки [math]V(p'_t, \Sigma \cup \{p'_t, p''_t\})[/math] или [math]V(p''_t, \Sigma \cup \{p'_t, p''_t\})[/math], то есть, можно опустить шаг поиска ближайшего соседа. Остаётся найти всю область конфликтов, как и в случае с точкой.

Случай сильно пересекающихся сайтов

Пусть [math]p[/math] — точка, которая сильно пересекается с отрезком [math]t_i[/math], т.е. [math]p \in t^\circ[/math]. Понятно, что [math]t^\circ[/math] будет ближайшим соседом [math]p[/math] в [math]\Sigma[/math]. Пусть [math]e'_i(p)[/math] и [math]e''_i(p)[/math] — два ребра [math]V(t^\circ, \Sigma)[/math], которые пересекаются с нормалями к [math]t[/math], проведёнными из точки [math]p[/math] (см. рисунок). Пусть [math]v'_i(p)[/math] и [math]v''_i(p)[/math] — точки пересечения нормалей с рёбрами [math]e'_i(p)[/math] и [math]e''_i(p)[/math] соответственно. Тогда алгоритм вставки точки [math]p[/math] в диаграмму [math]V(\Sigma)[/math] будет выглядеть следующим образом: Начинаем с поиска ближайшего соседа [math]N_\Sigma(p)[/math]. Если [math]N_\Sigma(p) = p[/math], то ничего не делаем. Если [math]N_\Sigma(p)[/math] — точка, или отрезок, с которым [math]p[/math] не пересекается, то запускается процедура вставки, которая была описана выше. Иначе [math]N_\Sigma(p) = t_i^\circ[/math] — отрезок, пересекающийся с [math]p[/math]. Сначала добавляем [math]p[/math] в [math]\Sigma[/math] и заменяем [math]t_i^\circ[/math] двумя отрезками [math]p'_ip[/math] и [math]pp''_i[/math], где [math]p'_i[/math] и [math]p''_i[/math] — конечные точки [math]t_i[/math]. Затем ищем рёбра [math]e'_i(p)[/math] и [math]e''_i(p)[/math], разбиваем их в точках [math]v'_i(p)[/math] и [math]v''_i(p)[/math] и добавляем отрезки [math]v'_i(p)p[/math] и [math]v''_i(p)p[/math] в диаграмму.

Если же мы хотим вставить в диаграмму отрезок [math]t[/math], то вставляем сначала его крайние точки [math]p'_t[/math] и [math]p''_t[/math]. Затем, начиная с [math]p'_t[/math], ищем первый конфликт [math]t^\circ[/math] с текущей диаграммой Вороного и ищем всю область конфликтов. Во время этого поиска, прежде чем тестировать ребро Вороного [math]e[/math] существующей диаграммы на потенциальный конфликт, мы проверяем, не пересекается ли [math]t^\circ[/math] с одним из сайтов, связанных с [math]e[/math]. Если такой сайт [math]S_i[/math] найден, то поиск останавливается. Если [math]S_i[/math] — точка, [math]p_i[/math], то вставляем отрезки [math]p'_tp_i[/math] и [math]p_ip''_t[/math] рекурсивно. Если [math]S_i[/math] — отрезок [math]t^\circ_i[/math], то сначала проверяем, не принадлежит ли один из [math]t^\circ[/math], [math]t^\circ_i[/math] другому. Если так и есть, то прекращаем работу, иначе вычисляем точку пересечения [math]p_+[/math] отрезков [math]t^\circ[/math] и [math]t^\circ_i[/math], вставляем её в диаграмму, а затем рекурсивно вставляем отрезки [math]p'_tp_+[/math] и [math]p_+p''_t[/math].

Время работы данного алгоритма составляет [math]O((n + m)\log^2m)[/math], где [math]n[/math] — количество элементов во входном множестве [math]\Sigma_I[/math], а [math]m[/math] — количество пар сильно пересекающихся сайтов.

Ссылки

• Menalaos I. Karavelas A robust and efficient implementation for the segment Voronoi diagram.
• Rolf Klein Randomized incremental construction of abstract Voronoi diagrams.