Изменения

{{В разработке}}== Определения ====Обозначения и определения= Совсем неформальное определение ==='''Сайт''' (''site'') {{[[Файл:voronoi---}} общее название diagram.png|200px|thumb|right|Пример диаграммы Вороного]]Пусть есть карта города, на которой точками обозначены почтовые отделения. Человек хочет отправить письмо, и он пойдёт на ближайшую почту. Ему интересно знать, какое отделение ближе, для любой точки <tex>p</tex> или замкнутого отрезка <tex>t</tex>города — необходимость отправить письмо может наступить неожиданно. Для этого он может взять карту и расчертить её на ячейки так, чтобы внутри каждой ячейки находилось только одно отделение, а для всех остальных точек ячейки именно эта почта была ближайшей. Полученная картинка и будет диаграммой Вороного для точек-почт.

=== Неформальное определение ===Есть множество точек <tex>t^\circP</tex> {{---}} внутренняя часть отрезкана плоскости. Внутренность Кусочек плоскости из точек <tex>q</tex> такой, что для всех <tex>q</tex> ближайшей точкой из множества <tex>P</tex> является одна и та же точка <tex>p</tex>, называется ячейкой Вороного точки {{---}} пустое множество<tex>p</tex>. Разбиение плоскости на такие ячейки для всех точек <tex>p_i \in P</tex> называется диаграммой Вороного для множества <tex>P</tex>.

Два замкнутых пересекающихся сайта '''слабо пересекаются''' (''weakly intersect'')=== Формальное определение ===<tex>P = \{ p_1, если точка их пересечения не принадлежит их внутренностямp_2, то есть они касаются концами..., p_n\}</tex> — множество точек на плоскости.

Два {{Определение|definition=<tex>p_i \in P</tex> называется '''сайтом''' (''site'').}} {{Определение|definition='''Ячейка Вороного''' (''Voronoi cell'', <tex>\mathcal{V}(p_i)</tex>) — множество точек плоскости <tex>q</tex> таких, что для фиксированного сайта <tex>p_i</tex> и любых других сайтов <tex>p_j \in P, \ j \neq i</tex> верно неравенство <tex>\rho(q, p_i) < \rho(q, p_j)</tex>.}} {{Определение|definition='''сильно пересекаютсяДиаграмма Вороного''' (''strongly intersectVoronoi diagram'', <tex>Vor(P)</tex>) для сайтов <tex>P = \{ p_1, p_2, ..., p_n\}</tex> на плоскости — это разбиение плоскости на ячейки Вороного для каждого сайта из <tex>P</tex>.}} В зависимости от контекста будем называть диаграммой Вороного как разбиение на ячейки, так и [[Основные определения теории графов|граф]] из вершин и рёбер, составляющих эти ячейки. == Свойства ===== Связь с пересечением полуплоскостей ===Возьмём две точки плоскости: <tex>p</tex> и <tex>q</tex>. Проведём серединный перпендикуляр к отрезку <tex>pq</tex>; полученную полуплоскость, которая содержит в себе <tex>p</tex>, обозначим <tex>h(p, q)</tex>, другую — <tex>h(q, p)</tex>. Заметим, что для точки <tex>r</tex> выполняется <tex>r \in h(p, q)</tex> тогда и только тогда, когда <tex>\rho(r, p) < \rho(r, q)</tex>. Отсюда вытекает следующее:{{Утверждение|id=intersect|statement=<tex>\mathcal{V}(p_i) = \bigcap\limits_{1 \leqslant j \leqslant n, j \neq i} h(p_i, p_j)</tex>}}Отсюда получаем, что ячейка Вороного — это пересечение <tex>n - 1</tex> полуплоскостей, и поэтому представляет собой (возможно, неограниченную) открытую выпуклую область с не более чем <tex>n - 1</tex> вершинами и <tex>n - 1</tex> рёбрами. === Топология диаграммы Вороного ==={{Теорема|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|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>. Пришли к противоречию. Докажем теперь, что диаграмма связна. Предположим, что это не так. Тогда на её рёбрах найдутся две точки <tex>s</tex> и <tex>t</tex>, между которыми нет пути по рёбрам диаграммы. Рассмотрим отрезок <tex>st</tex>. Он пересекает некоторое количество ячеек диаграммы. Пусть он пересекает какую-то ячейку в точках <tex>a</tex> и <tex>b</tex>. От точки <tex>a</tex> до точки <tex>b</tex> можно добраться по рёбрам тогда и только тогда, когда ячейка связна. Раз пути из <tex>s</tex> в <tex>t</tex> нет, то какая-то из ячеек, пересекаемых отрезком <tex>st</tex>, несвязная. Это возможно, только если она представляет собой полосу, ограниченную двумя параллельными прямыми. Но в нашем случае в диаграмме не может быть прямых, пришли к противоречию. [[Файл:voronoi-connected.png|500px]]}} === Размер структуры ==={{Теорема|statement=Для <tex>n \geqslant 3</tex> сайтов диаграмма Вороного содержит не больше <tex>2n - 5</tex> вершин и <tex> 3n - 6</tex> рёбер.|proof=[[Файл:voronoi-infinite-vertex.png|200px|right]]Для случая сайтов, лежащих на одной прямой, утверждение напрямую следует из вида диаграммы для этого случая, поэтому рассмотрим общий случай. По [[Формула Эйлера|формуле Эйлера]] <tex>v - e + f = 2</tex>, где <tex>v</tex> — число вершин, <tex>e</tex> — число рёбер и <tex>f</tex> — число граней связного планарного графа. Мы не можем сразу применить эту формулу к <tex>Vor(P)</tex>, потому что в этом графе есть полубесконечные рёбра. Поэтому добавим вершину <tex>v_\infty</tex>, и все полубесконечные рёбра мы превратим в рёбра, инцидентные ей. Таким образом мы увеличили число вершин на одну, а число рёбер не изменилось. Число граней равно <tex>n</tex> по определению диаграммы Вороного. Тогда по формуле Эйлера получаем <tex>(v + 1) - e + n = 2</tex>.Сумма степеней всех вершин полученного графа равна <tex>2e</tex>, так как у каждого ребра есть ровно два конца (нет петель). Также из каждой вершины исходят как минимум три ребра. Отсюда получаем <tex>2e \geqslant 3 (v + 1)</tex>.Домножим равенство на два и вычтем из него полученную нижнюю границу для <tex>2 \cdot e</tex>, в результате получим <tex> v \leqslant 2n - 5</tex>. Далее подставим этот результат в равенство и получим <tex>e \leqslant 3n - 6</tex>, что и требовалось доказать.}} === Связь с триангуляцией Делоне ==={{Определение|definition='''Наибольшая пустая окружность''' точки <tex>q</tex> по отношению к <tex>P</tex> (''largest empty circle of ''<tex>q</tex>'' with respect to ''<tex>P</tex>, <tex>C_P(q)</tex>) — наибольшая окружность с центром в <tex>q</tex> такая, что во внутренности хотя бы соответствующего ей круга не лежит ни одного сайта из данных <tex>P</tex>.}} {{Лемма|statement=Точка <tex>q</tex> — вершина диаграммы Вороного в том и только в том случае, когда <tex>C_P(q)</tex> содержит три и более сайтов на своей границе.|proof=Предположим, что <tex>q</tex> существует, а <tex>p_i, \ p_j, \ p_k</tex> — соответствующие точки. Так как внутри <tex>C_P(q)</tex> нет других сайтов, а <tex>q</tex> равноудалена от точек <tex>p_i, \ p_j, \ p_k</tex>, <tex>q</tex> должна быть на границе <tex>\mathcal{V}(p_i), \ \mathcal{V}(p_j), \ \mathcal{V}(p_k)</tex> одновременно, то есть вершиной диаграммы.Докажем в другую сторону: каждая вершина <tex>q</tex> диаграммы инцидентна минимум трём рёбрам, и, поэтому, как минимум трём ячейкам <tex>\mathcal{V}(p_i), \ \mathcal{V}(p_j), \ \mathcal{V}(p_k)</tex>. Тогда <tex>q</tex> лежит на равном расстоянии от <tex>p_i, \ p_j, \ p_k</tex> и не может быть другого сайта ближе к <tex>q</tex>, так как иначе <tex>\mathcal{V}(p_i), \ \mathcal{V}(p_j), \ \mathcal{V}(p_k)</tex> не сойдутся в <tex>q</tex>. Поэтому можно построить окружность с центром в <tex>q</tex> и <tex>p_i, \ p_j, \ p_k</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|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> (так как <tex>q</tex> равноудалена от <tex>p_i</tex> и <tex>p_j</tex>). Также эта окружность не должна содержать никаких других сайтовна границе, так как тогда она является вершиной.}}

Расстояние от точки {{Теорема|statement=Если соединить все сайты, соответствующие смежным ячейкам диаграммы Вороного, получится [[триангуляция Делоне]] для этого множества точек.|proof=Если ячейки, соответствующие сайтам <tex>x p_i, \in \mathbb{E}^2p_j</tex>, смежны, то серединный перпендикуляр к отрезку <tex>p_i p_j</tex> до замкнутого сайта образует ребро диаграммы Вороного, то есть к нему применима предыдущая лемма и можно построить окружность с <tex>S_ip_i</tex>: и <tex>p_j</tex>\deltaна границе, внутри которой не будет других сайтов. Триангуляции Делоне принадлежат [[Триангуляция Делоне#Критерий Делоне для рёбер|те и только те]] рёбра (xс поправкой на точки, S_iлежащие на одной окружности) = \min{\{||x - y|| : y \in S_i\}}, на которых можно построить такую окружность, что внутри неё не будет лежать никаких точек. Тогда ребро <tex>p_i p_j</tex>является ребром триангуляции Делоне.За счёт равносильности в обеих используемых леммах мы добавим все рёбра и не построим лишних.}}

Пусть <tex>H_{ij} = \{x \in \mathbb{E}^2 : \delta(x= Построение ===== Наивный алгоритм ===Будем [[Пересечение полуплоскостей, S_i) \le \delta(x, S_j)\}</tex>связь с выпуклыми оболочками|пересекать полуплоскости]] по [[#intersect|свойству ячейки диаграммы]]. '''Ячейка Вороного''' (''Voronoi cell'') Необходимо для каждого сайта пересечь <tex>V(S_i, \Sigma)</tex> {{--n -}} множество точек, которые находятся ближе к <tex>S_i1</tex>плоскость, чем к любому другому сайту, то есть что суммарно делается за <tex>VO(S_i, n^2 \Sigmalog n) = \cap_{i \ne j}H_{ij}</tex>.

'''Ребро Вороного''' === Инкрементальный алгоритм ===Храним диаграмму в [[ППЛГ и РСДС (''Voronoi edge''PSLG и DCEL) : определение, построение РСДС множества прямых|РСДС]]. Пусть у нас уже есть диаграмма для точек <tex>p_1, p_2, ..., p_i</tex>. Добавим новый сайт <tex>p_{i+1}</tex>. Сначала найдём сайт <tex>p_j</tex>, в ячейку которого попадает <tex>p_{---i+1}</tex>, перебором. После этого строим новую ячейку: сначала проведём серединный перпендикуляр для <tex>p_{i+1} связное множество точекp_j</tex>, принадлежащих пересечению ровно двух ячеек Вороногоон пересечёт границу ячейки <tex>\mathcal{V}(p_j)</tex> с ячейкой <tex>\mathcal{V}(p_k)</tex>; на следующем шаге будем строить серединный перпендикуляр для <tex>p_{i+1} p_k</tex> и так далее.

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

* создаём вершину <tex>v</tex> с полуребром <tex>e</tex>;* для полуребра <tex>e</tex> в РСДС второй конец в вершине <tex>v</tex>, следующее полуребро — <tex>e'''1-каркас''' </tex>, инцидентные грани — слева <tex>\mathcal{V}(''i+1-skeleton'') </tex>, справа — <tex>V_1\mathcal{V}(\Sigmaj)</tex> ;* добавляем в РСДС полуребро <tex>e + 1</tex> с началом в <tex>v</tex> и предыдущим полуребром <tex>e</tex>;* удаляем все полурёбра, лежащие между вершиной начала <tex>e</tex> и вершиной конца <tex>e</tex>, по часовой стрелке;* обновляем полуребро, соответствующее грани для <tex>\mathcal{{---V}} набор вершин и рёбер Вороного(p_j)</tex> — им становится <tex>e</tex>.

В процессе работы алгоритма множество сайтов, которые подаются на вход, может измениться. Чтобы различать начальное и конечное множество сайтов, будем обозначать входное множество через Каждый шаг выполняется за <tex>\Sigma_IO(i)</tex>, а множество сайтовзначит, которые присутствуют на результирующей диаграмме Вороного, через <tex>\Sigmaсуммарно диаграмма из </tex>. <tex>\Sigma_In</tex> всегда состоит из замкнутых сайтов, а с нуля создаётся за <tex>\SigmaO(n^2)</tex> {{---}} из точек и открытых отрезков.

Пусть сайты <tex>S_i</tex> и <tex>S_j</tex> слабо пересекаются. Тогда '''битангентная окружность Вороного''' (''bitangent Voronoi circle'') <tex>C_{ij}</tex> {{||[[Файл:voronoi-incremental-zero-}} окружность, касающаяся одновременно <tex>S_i</tex> и <tex>S_j</tex>step. При рассмотрении трёх сайтов <tex>S_i</tex>, <tex>S_j</tex> и <tex>S_k</tex>, окружность, касающаяся всех трёх сайтов, называется '''тритангентной окружностью Вороного''' (''tritangent Voronoi circle'')png|200px|thumb|Локализация]]|[[Файл:voronoi-incremental-first-step. Точки, принадлежащие рёбрам Вороного, являются центрами битангентных окружностей, а вершины {{png|200px|thumb|Добавление первого ребра]]|[[Файл:voronoi-incremental.png|200px|thumb|Добавление третьего ребра]]|[[Файл:voronoi-update-dcel.png|400px|thumb|Обновление структуры при добавлении ребра]]|}} тритангентных.

Рассмотрим <tex>S \notin \Sigma_I</tex>=== Алгоритм Форчуна ===Построение производится при помощи заметающей прямой и парабол позади неё (параболы в данном случае - это множества точек, равноудалённых от вершины и прямой). Сама диаграмма "рисуется" местами соприкасания соседних парабол. Будем говоритьНесмотря на то, что <tex>S</tex> '''конфликтует''' с окружностью Вороного <tex>C</tex>в теории движение прямой происходит непрерывно, сам алгоритм обрабатывает только крайние случаи, когда происходят события. Рассматривается 2 типа событий - появление новой параболы, если <tex>S</tex> пересекается с кругомкогда заметающая прямая касается вершины, ограниченным <tex>C</tex>и схлопывание параболы - когда две соседние параболы её полностью накрывают. Также Всего событий <tex>S</tex> конфликтует с ребром <tex>e \in VO(S, \Sigman)</tex>, если он пересекается с кругом, ограниченным одной из окружностей Вороного с центром в точке, принадлежащей (<tex>en</tex>- число вершин). '''Область конфликтов''' Для каждого события вычисляется его время (''conflict region''позиция заметающей прямой) <tex>R_\Sigma, события кладутся в очередь с приоритетом (S)отсюда </tex> {{---}} множество точек 1-каркаса <tex>V_1O(\Sigmalog n)</tex>по времени) и обрабатываются, соответствующих окружностям Вороногопока очередь непуста. При обработке событий также записываются пары взаимодействующих вершин (у которых сайты имеют общую границу), которые конфликтуют с <tex>S</tex>это и является результатом работы алгоритма.

==Алгоритм==Рассмотрим сначала алгоритм для слабо пересекающихся сайтов, а потом обобщим его для случая сильно пересекающихся сайтовСложность работы алгоритма - <tex>O(n \log n)</tex> по времени и <tex>O(n)</tex> по памяти.

===Случай слабо пересекающихся сайтов===Более подробно:Пусть мы уже построили диаграмму Вороного для некоторого множества <tex>\Sigma<* [https:/tex>/ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A4%D0%BE%D1%80%D1%87%D1%83%D0%BD%D0%B0 Описание алгоритма на Wikipedia]* [https://www2.cs.sfu.ca/~binay/813. Рассмотрим процедуру вставки нового сайта <tex>S<2011/tex>Fortune.pdf Презентация с описанием в деталях]

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

== Диаграмма k-го порядка =={{Определение|definition='''1Ячейка Вороного'''. Найти первый конфликт сайта <tex>Sk</tex> с каркасом '''-го порядка''' (<tex>V_1\mathcal{V}_k(\Sigmap_1, p_2, ..., p_k)</tex>)— множество точек, имеющих в качестве ближайших <tex>k</tex> соседей множество сайтов <tex>p_1, p_2, ..., p_k</tex>.}}

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

'''Итого совершаем <tex>k</tex> шагов, на каждом строим <tex>O(n)</tex> диграмм Вороного за время <tex>O(n^3''')</tex>, пересекаем <tex>O(n)</tex> ячеек с <tex>O(n)</tex> ячейками за <tex>O(n)</tex> времени, а потом объединяем ячейки за <tex>O(n)</tex> (линейное количество соседних рёбер ячейки, а объединение происходит за <tex>O(1)</tex> за счёт структуры РСДС). Построить диаграмму Вороного для Итого <tex>O(k \Sigma \cup \{S\} cdot n^3)</tex>.

'''4'''{||[[Файл:voronoi-first-order. Обновить локализационную структуруpng|200px|thumb|Диаграмма первого порядка]]|[[Файл:voronoi-second-order.png|200px|thumb|Диаграмма второго порядка]]|[[Файл:voronoi-third-order.png|200px|thumb|Диаграмма третьего порядка]]|[[Файл:voronoi-tenth-order.png|200px|thumb|Диаграмма <tex>n - 1</tex>-го порядка (она же farthest-point диаграмма) для данного набора сайтов]]|}

|statement=<tex>\Sigma</tex> {{---}} слабо пересекающееся между собой множество сайтов. Тогда <tex>\forall s \in \Sigma</tex> ячейки Вороного <tex>V(s, \Sigma)</tex> {{---}} односвязные множества.|proof=Для начала докажем, что ячейки связны. Пусть это не так и у ячейки любой точки <tex>V(s, \Sigma)q</tex> несколько компонент связности. Рассмотрим <tex>\varepsilon</tex> {{---}} одну плоскости самый удалённый от неё сайт из тех, которая не содержит в себе <tex>s</tex>. Начнём идти по кратчайшему пути <tex>P</tex> от любой точки <tex>p \in \varepsilon</tex> до <tex>s</tex>. Так как <tex>p</tex> и <tex>s</tex> лежат в разных компонентах связности, найдётся <tex>s' \in \Sigma</tex>должен лежать на [[Статические выпуклые оболочки: Джарвис, такой что путь <tex>P</tex> проходит через <tex>V(s'Грэхем, \Sigma)</tex>. Значит существует путь от <tex>p</tex> до <tex>s'</tex>Эндрю, который корочеЧен, чем QuickHull|выпуклой оболочке]] <tex>P</tex>, следовательно и <tex>\delta(p, s') < \delta(p, s) .|proof= [[Файл:voronoi-farthest-inside.png|P200px|</tex>. Противоречиеright]]Сайт, не находящийся на выпуклой оболочке, лежит внутри неё по свойствам выпуклой оболочки.

Теперь допустим, что Пусть самый удалённый от точки <tex>V(s, \Sigma)q</tex> содержит разрыв в виде другой ячейки сайт <tex>V(s', \Sigma)p_i</tex>не лежит на выпуклой оболочке (т.е. Проверём прямую, которая соответствует кратчайшему расстоянию между <tex>s</tex> и <tex>s'</tex> и рассмотрим точку <tex>p</tex>, которая лежит на её продолжении за внутри неё). Проведём луч <tex>s'q p_i</tex> и принадлежит . Он пересечёт ребро выпуклой оболочки <tex>V(s, \Sigma)p_j p_k</tex>. Такая точка будет существоватьПолучатся два смежных угла, рассмотрим тот, т.ккоторый оказался прямым или тупым. Тогда в полученном треугольнике <tex>V\rho(s'q, \Sigmap_j)</tex> лежит внутри <tex>V\rho(sq, \Sigmap_i)</tex>. Получаем, что кратчайший путь от <tex>p</tex> до <tex>s</tex> проходит через <tex>s'</tex>так как напротив большего угла лежит большая сторона. Опять противоречиеПришли к противоречию.

{|border="0" width="100%"|{{ТеоремаЛемма|statement=Сайт, который лежит внутри выпуклой оболочки сайтов, не может иметь ячейку в farthest-point диаграмме.|proof=Пусть это не так и сайт <tex>\Sigmap</tex> {{лежит внутри выпуклой оболочки и имеет ячейку в farthest---}} множество слабо пересекающихся сайтов, <tex>s</tex> {{---}} сайт, point диаграмме. Тогда внутри неё есть точка <tex>s \notin \Sigmaq</tex>. Тогда Но по предыдущей лемме самый удалённый для <tex>R_\Sigma(s)q</tex> {{---}} связное непустое множество.|proof=Пусть сайт лежит на выпуклой оболочке, а значит, сайт <tex>C = V(s, \Sigma \cup \{s\})p</tex>, не может быть самым удалённым для <tex>R_\Sigma(s) = \varepsilonq</tex>. Пришли к противоречию.}}

Заметим, что <tex>\varepsilon {{Лемма|statement= V_1(\Sigma) \cap C</tex>. Если бы область конфликтов <tex>\varepsilon</tex> была пустойКаждый сайт, то было бы верно <tex>C \subset V(qкоторый является вершиной выпуклой оболочки сайтов, \Sigma \cup \{p\})</tex> для некоторого <tex>q \in \Sigma</tex> и <tex>V(q, \Sigma \cup s)</tex> не было бы односвязнымимеет ячейку в farthest-point диаграмме.|proof=Докажем по индукции.

Пусть <tex>\varepsilon_1, \varepsilon_2, ... , \varepsilon_k</tex> {{--База индукции: для двух сайтов они оба являются вершинами выпуклой оболочки и оба имеют ячейку в farthest-}} связные компоненты <tex>\varepsilon</tex> для некоторого <tex>k</tex>point диаграмме (дальняя от сайта полуплоскость).

Предположим, что Переход: добавим сайт <tex>k \ge 2</tex>. Тогда cуществует путь <tex>P \subseteq C \setminus \varepsilonp</tex>так, соединяющий две точки <tex>x</tex> и <tex>y</tex> на границе <tex>C</tex> и отделяющий <tex>\varepsilon_1</tex> от <tex>\varepsilon_2</tex>(смчто он станет новой вершиной выпуклой оболочки. рисунок). <tex>P \cap \varepsilon = \varnothing \Rightarrow P \cap V_1(\Sigma) = \varnothing \Rightarrow P \subseteq intV(q, \Sigma)</tex> для некоторого <tex>q \in \Sigma</tex>. <tex>x, y \in P \Rightarrow</tex> все достаточно малые окрестности <tex>U(x)</tex>, <tex>U(y)</tex> полностью содержатся Пусть он не имеет ячейку в <tex>V(qfarthest-point диаграмме, \Sigma)</tex>то есть уже имеющаяся перед его добавлением диаграмма не меняется. ЗначитДля построения farthest-point диаграммы проводятся серединные перпендикуляры между всеми парами сайтов, точки пересечения этих окрестностей с дополнением <tex>C</tex> лежат в <tex>V(q, \Sigma \cup s)</tex> и могут быть соединены путём <tex>L \subseteq V(q, \Sigma \cup \{s\}) \subseteq V(q, \Sigma)</tex>. Следовательнополученные полуплоскости пересекаются; раз новой ячейки не добавилось, цикл то серединные перпендикуляры между <tex>P \circ L</tex> полностью содержится в <tex>V(q, \Sigma)p</tex> и содержит <tex>\varepsilon_1</tex> или <tex>\varepsilon_2</tex> в своей внутренней частиостальными сайтами совпали с уже имеющимися перпендикулярами. Это противоречит томувозможно, что только если <tex>V(q, \Sigma)</tex> {{---}} односвязное множество, следовательно <tex>k = 1p</tex>совпал с другим сайтом. Пришли к противоречию.

Таким образом{{Утверждение|statement=Сайт имеет ячейку в farthest-point диаграмме тогда и только тогда, для нахождения области конфликтов, можно найти одно конфликтующее ребро, а затем, при помощи DFS, найти все остальныекогда он является вершиной выпуклой оболочки всех сайтов.|proof=Непосредственно следует из двух предыдущих лемм.}}

{{Утверждение|statement=Все ячейки в farthest-point диаграмме неограничены.|proof=[[Файл:voronoi-farthest-unbounded.png|200px|right]]Пусть <tex>p_i</tex> — сайт на выпуклой оболочке сайтов, а <tex>Sq</tex> {{---}} это — точка , для которой он является наиболее удалённым. Тогда для всех точек на луче, лежащем на <tex>pp_i q</tex>, начинающемся в <tex>q</tex> и не проходящим через <tex>p_i</tex>, сайт <tex>p_i</tex> будет наиболее удалённым среди остальных сайтов.Значит, ячейка сайта <tex>p_i</tex> в farthest-point диаграмме включает в себя этот луч, а значит, неограничена.}}

Первый шаг алгоритма начинается с поиска ближайшего соседа <tex>N_\Sigma(p)</tex> точки p среди === Алгоритм ===Чтобы найти farthest-point диаграмму, сначала найдём выпуклую оболочку всех сайтов . Обозначим сайты, её образующие, через <tex>\Sigmap_1, p_2, ..., p_m</tex> (если есть несколько ближайших, то подойдёт любой из них). Будем хранить нашу диаграмму в скип-листе Запомним порядки обхода для того, чтобы можно было быстро выполнять эти запросы. Либо каждой вершины выпуклой оболочки по часовой стрелке (<tex>N_\Sigmacw(pp_i)</tex> ) и против часовой (<tex>p</tex> {{---}} это одна и та же точка, и ничего делать не нужно, либо <tex>p</tex> конфликтует хотя бы с одним ребром, принадлежащим границе ячейки <tex>V(N_\Sigmaccw(p)p_i)</tex>. Тогда первый шаг завершается рассмотрением границы <tex>V(N_\Sigma(p))</tex> и возвращением одного сделаем случайную перестановку точек. Далее удаляем из рёбервыпуклой оболочки все точки, конфликтующих с <tex>p</tex>кроме первых трёх (запоминая при этом их соседей в оболочке на момент удаления). Как было сказано раньше, второй шаг {{После этого строим farthest---}} DFS по рёбрам <tex>V_1point диаграмму для первых трёх точек (\Sigmaпересекая полуплоскости)</tex> с целью найти все рёбра, конфликтующие с точкой <tex>p</tex>. После того, как мы узнали <tex>R_\Sigmaи последовательно добавляем остальные (pудалённые)</tex>, третий шаг будет заключаться в создании новой ячейки Вороногопорядке, имеющей границу <tex>R_\Sigma(p)</tex>обратном порядку удаления.

Если же <tex>S</tex> {{-||[[Файл:voronoi-farthest-}} это замкнутый отрезок <tex>t</tex>, то сначала вставляем конечные точки <tex>p'_t</tex> и <tex>p''_t</tex>, используя процедуру, описанную вышеconstruct. Остаётся вставить открытый отрезок <tex>t^\circ</tex>. Так как <tex>p'_t</tex> и <tex>p''_t</tex> {{--png|600px|thumb|Построение очередной ячейки farthest-point диаграммы]]|}} соседи <tex>t^\circ</tex> в диаграмме <tex>V(\Sigma \cup \{p'_t, p''_t, t^\circ\})</tex>, <tex>t^\circ</tex> обязан конфликтовать с каким-нибудь ребром ячейки, соответствующей <tex>p'_t</tex> или <tex>p''_t</tex>. Таким образом, первый конфликт <tex>t^\circ</tex> с <tex>V_1(\Sigma \cup \{p'_t, p''_t\})</tex> можно найти, просматривая рёбра ячейки <tex>V(p'_t, \Sigma \cup \{p'_t, p''_t\})</tex> или <tex>V(p''_t, \Sigma \cup \{p'_t, p''_t\})</tex>, то есть, можно опустить шаг поиска ближайшего соседа. Остаётся найти всю область конфликтов, как и в случае с точкой.

===Случай сильно пересекающихся сайтов==={|border="0" width="100%"|Пусть Для точки <tex>pp_i</tex> {{---}} точкаячейка встанет «между» ячейками, которая сильно пересекается с отрезком соответствующими <tex>t_icw(p_i)</tex>, т.е. и <tex>p \in t^\circccw(p_i)</tex>. Понятно, что <tex>t^\circ</tex> будет ближайшим соседом Перед добавлением <tex>pp_i</tex> в <tex>\Sigma</tex>. Пусть <tex>e'_icw(pp_i)</tex> и <tex>e''_iccw(pp_i)</tex> {{---}} два ребра — соседи, поэтому между ними построен серединный перпендикуляр. Серединный перпендикуляр к <tex>Vp_i ccw(t^\circ, \Sigmap_i)</tex>даст новое ребро, которые пересекаются с нормалями к которое лежит в farthest-point ячейке <tex>tccw(p_i)</tex>, проведёнными из точки и является частью границы ячейки <tex>pp_i</tex> (см. рисунок). Пусть Обойдём ячейку <tex>v'_iccw(pp_i)</tex> и <tex>v''_i(p)</tex> {{по часовой стрелке, чтоб понять, какое ребро пересечёт перпендикуляр. С другой стороны этого ребра лежит ячейка какой---}} то точки пересечения нормалей с рёбрами <tex>e'_i(p)p_j</tex> , и серединный перпендикуляр <tex>e''_i(p)p_i p_j</tex> соответственно. Тогда алгоритм вставки точки тоже даст ребро ячейке <tex>pp_i</tex> в диаграмму . Аналогично совершим обход и так далее. Последний серединный перпендикуляр будет построен для <tex>Vp_i cw(\Sigmap_i)</tex> будет выглядеть следующим образом:. После этого удаляем рёбра, которые лежат внутри новой ячейки.

Начинаем с поиска ближайшего соседа <tex>N_\Sigma(p)</tex>== См. Если <tex>N_\Sigma(p) также = p</tex>, то ничего не делаем. Если <tex>N_\Sigma(p)</tex> {{---}} точка, или отрезок, с которым <tex>p</tex> не пересекается, то запускается процедура вставки, которая была описана выше. Иначе <tex>N_\Sigma(p) = t_i^\circ</tex> {{---}} отрезок, пересекающийся с <tex>p</tex>. Сначала добавляем <tex>p</tex> в <tex>\Sigma</tex> и заменяем <tex>t_i^\circ</tex> двумя отрезками <tex>p'_ip</tex> и <tex>pp''_i</tex>, где <tex>p'_i</tex> и <tex>p''_i</tex> {{---}} конечные точки <tex>t_i</tex>. Затем ищем рёбра <tex>e'_i(p)</tex> и <tex>e''_i(p)</tex>, разбиваем их в точках <tex>v'_i(p)</tex> и <tex>v''_i(p)</tex> и добавляем отрезки <tex>v'_i(p)p</tex> и <tex>v''_i(p)p</tex> в диаграмму.||* [[Трапецоидная карта]]* [[Файл:strongly_intersect.png|300px|thumb|rightТриангуляция Делоне]]|}* [[Straight skeleton]]

Если же мы хотим вставить в диаграмму отрезок <tex>t</tex>== Источники ==* de Berg, то вставляем сначала его крайние точки <tex>p'_t</tex> и <tex>p''_t</tex>. ЗатемCheong, начиная с <tex>p'_t</tex>van Kreveld, ищем первый конфликт <tex>t^\circ</tex> с текущей диаграммой Вороного и ищем всю область конфликтовOvermars. Во время этого поискаComputational Geometry, прежде чем тестировать ребро Вороного <tex>e</tex> существующей диаграммы на потенциальный конфликтAlgorithms and Applicants, мы проверяем2008. pp. 147-151, не пересекается ли <tex>t^\circ<164-166* [http:/tex> с одним из сайтов, связанных с <tex>e</tex>students. Если такой сайт <tex>S_i<info.uaic.ro/tex> найден, то поиск останавливается~emilian. Если <tex>S_i<necula/tex> vor2.pdf Algorithms for constructing Voronoi diagrams, Vera Sacrist´an {{---}} точка, <tex>p_i<Incremental algorithm]* [http://en.wikipedia.org/wiki/tex>, то вставляем отрезки <tex>p'_tp_i<Voronoi_diagram Wikipedia — Voronoi diagram]* [https:/tex> и <tex>p_ip''_t</tex> рекурсивноweb.archive. Если <tex>S_i<org/web/tex> {{---}} отрезок <tex>t^\circ_i<20170329014016/tex>, то сначала проверяем, не принадлежит ли один из <tex>t^\circ<http:/tex>, <tex>t^\circ_i</tex> другомуwww. Если так и есть, то прекращаем работу, иначе вычисляем точку пересечения <tex>p_+</tex> отрезков <tex>t^\circ<cs.uu.nl/tex> и <tex>t^\circ_i<docs/tex>, вставляем её в диаграмму, а затем рекурсивно вставляем отрезки <tex>p'_tp_+<vakken/tex> и <tex>p_+p''_t<ga/tex>slides7b.pdf Computational Geometry {{---}} Lecture 13: More on Voronoi diagrams]