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

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

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

Сайт (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)[/math] — множество точек, которые находятся ближе к [math]S_i[/math], чем к любому другому сайту, то есть [math]V(S_i) = \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)[/math], если он пересекается с кругом, ограниченным одной из окружностей Вороного с центром в точке, принадлежащей [math]e[/math]. Область конфликтов (conflict region) [math]R_\Sigma(S)[/math] — множество точек 1-каркаса [math]V_1(\Sigma)[/math], соответствующих окружностям Вороного, которые конфликтуют с [math]S[/math].