418
правок
Изменения
Нет описания правки
{{Теорема
|statement=Пусть <tex>P</tex> — множество из <tex>n</tex> сайтов. Если они все лежат на одной прямой, то <tex>Vor(P)</tex> представляет собой <tex>n - 1</tex> параллельную прямую. Иначе <tex>Vor(P)</tex> связная и все её рёбра — либо отрезки, либо лучи.
|proof=[[Файл:voronoi-not-lines.png|200px|thumb|right]] В случае, если все сайты лежат на одной прямой, каждая пара соседних сайтов порождает серединный перпендикуляр к отрезку, содержащему их, и, соответственно, к прямой, которая содержит все сайты. Так получаются <tex>n - 1</tex> прямая, каждая из которых перпендикулярна прямой, содержащей сайты, а значит, эти прямые параллельны.
Рассмотрим теперь случай, когда сайты не лежат на одной прямой. Покажем, что рёбра — это отрезки или лучи, от противного. Предположим, что есть ребро <tex>e</tex>, являющееся прямой. Пусть оно — граница ячеек <tex>\mathcal{V}(p_i)</tex> и <tex>\mathcal{V}(p_j)</tex>. Пусть точка <tex>p_k \in P</tex> не лежит на прямой <tex>p_i p_j</tex> (по условию такая точка существует). Тогда серединный перпендикуляр к <tex>p_j p_k</tex> не параллелен <tex>e</tex>, и, значит, он его пересекает. Но тогда та часть <tex>e</tex>, что лежит в <tex>h(p_k, p_j)</tex>, не может быть границей <tex>\mathcal{V}(p_j)</tex>, потому что она ближе к <tex>p_k</tex>, чем к <tex>p_j</tex>. Пришли к противоречию.
{{Теорема
|statement=Для <tex>n \geqslant 3</tex> сайтов диаграмма Вороного содержит не больше <tex>2n - 5</tex> вершин и <tex> 3n - 6</tex> рёбер.
|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_\infty</tex>, и все полубесконечные рёбра мы превратим в рёбра, инцидентные ей. Таким образом мы увеличили число вершин на одну, а число рёбер не изменилось. Число граней равно <tex>n</tex> по определению диаграммы Вороного. Тогда по формуле Эйлера получаем <tex>(v + 1) - e + n = 2</tex>.
Сумма степеней всех вершин полученного графа равна <tex>2e</tex>, так как у каждого ребра есть ровно два конца (нет петель). Также у из каждой вершины исходят как минимум три ребра. Отсюда получаем <tex>2e \geqslant 3 (n + 1)</tex>.
Домножим равенство на два и вычтем из него полученную нижнюю границу для <tex>2 \cdot e</tex>, в результате получим <tex> v \leqslant 2n - 5</tex>. Далее подставим этот результат в равенство и получим <tex>e \leqslant 3n - 6</tex>, что и требовалось доказать.
{{Лемма
|statement=Серединный перпендикуляр к отрезку <tex>p_i p_j</tex> образует ребро диаграммы Вороного в том и только в том случае, если на нём есть точка <tex>q</tex> такая, что <tex>C_P(q)</tex> содержит на своей границе только сайты <tex>p_i, \ p_j</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>, и никаких других сайтов внутри.
}}
{|
|[[Файл:voronoi-incremental.png|200px|thumb|Процесс построения диаграммы при добавлении новой точки]]|[[Файл:voronoi-update-dcel.png|400px|thumb|Обновление структуры при добавлении ребра]]
|}
{|
|[[Файл:voronoi-farthest-construct.png|600px|thumb|Построение очередной ячейки farthest-point диаграммы]]
|}
