Изменения

{{В разработке}}== Определения ====Обозначения и определения= Совсем неформальное определение ==='''Сайт''' (''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>p_i, \ p_j</tex>, смежны, то серединный перпендикуляр к отрезку <tex>p_i p_j</tex> образует ребро диаграммы Вороного, то есть к нему применима предыдущая лемма и можно построить окружность с <tex>p_i</tex> и <tex>p_j</tex> на границе, внутри которой не будет других сайтов. Триангуляции Делоне принадлежат [[Триангуляция Делоне#Критерий Делоне для рёбер|те и только те]] рёбра (с поправкой на точки, лежащие на одной окружности), на которых можно построить такую окружность, что внутри неё не будет лежать никаких точек. Тогда ребро <tex>p_i p_j</tex> является ребром триангуляции Делоне. За счёт равносильности в обеих используемых леммах мы добавим все рёбра и не построим лишних.}}

Расстояние от точки <tex>x \in \mathbb{E}^2</tex> до замкнутого == Построение ===== Наивный алгоритм ===Будем [[Пересечение полуплоскостей, связь с выпуклыми оболочками|пересекать полуплоскости]] по [[#intersect|свойству ячейки диаграммы]]. Необходимо для каждого сайта пересечь <tex>S_in - 1</tex>: плоскость, что суммарно делается за <tex>O(n^2 \delta(x, S_ilog n) = \min{\{||x - y|| : y \in S_i\}}</tex>.

=== Инкрементальный алгоритм ===Храним диаграмму в [[ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых|РСДС]]. Пусть у нас уже есть диаграмма для точек <tex>H_{ij} = \{x \in \mathbb{E}^2 : \delta(xp_1, p_2, S_i) \le \delta(x..., S_j)\p_i</tex>. Добавим новый сайт <tex>p_{i+1}</tex>. '''Ячейка Вороного''' (''Voronoi cell'') Сначала найдём сайт <tex>p_j</tex>V(S_i, \Sigma)в ячейку которого попадает </tex> p_{{---i+1}} множество точек</tex>, которые находятся ближе к перебором. После этого строим новую ячейку: сначала проведём серединный перпендикуляр для <tex>S_ip_{i+1}p_j</tex>, чем к любому другому сайту, то есть он пересечёт границу ячейки <tex>\mathcal{V}(S_i, \Sigmap_j) = </tex> с ячейкой <tex>\cap_mathcal{i \ne jV}H_(p_k)</tex>; на следующем шаге будем строить серединный перпендикуляр для <tex>p_{iji+1}p_k</tex>. Ячейки Вороного односвязныи так далее.

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

'''1-каркас''' Каждый шаг выполняется за <tex>O(''1-skeleton''i) </tex>, значит, суммарно диаграмма из <tex>n</tex> сайтов с нуля создаётся за <tex>V_1O(\Sigman^2)</tex> {{---}} набор вершин и рёбер Вороного.

В процессе работы алгоритма множество сайтов, которые подаются на вход, может измениться{||[[Файл:voronoi-incremental-zero-step. Чтобы различать начальное и конечное множество сайтов, будем обозначать входное множество через <tex>\Sigma_I</tex>, а множество сайтов, которые присутствуют на результирующей диаграмме Вороного, через <tex>\Sigma</tex>png|200px|thumb|Локализация]]|[[Файл:voronoi-incremental-first-step. <tex>\Sigma_I</tex> всегда состоит из замкнутых сайтов, а <tex>\Sigma</tex> {{png|200px|thumb|Добавление первого ребра]]|[[Файл:voronoi-incremental.png|200px|thumb|Добавление третьего ребра]]|[[Файл:voronoi-update-dcel.png|400px|thumb|Обновление структуры при добавлении ребра]]|}} из точек и открытых отрезков.

Пусть сайты <tex>S_i</tex> === Алгоритм Форчуна ===Построение производится при помощи заметающей прямой и <tex>S_j</tex> слабо пересекаются. Тогда '''битангентная окружность Вороного''' парабол позади неё (''bitangent Voronoi circle''параболы в данном случае - это множества точек, равноудалённых от вершины и прямой) <tex>C_{ij}</tex> {{. Сама диаграмма "рисуется" местами соприкасания соседних парабол. Несмотря на то, что в теории движение прямой происходит непрерывно, сам алгоритм обрабатывает только крайние случаи, когда происходят события. Рассматривается 2 типа событий -появление новой параболы, когда заметающая прямая касается вершины, и схлопывание параболы --}} окружность, касающаяся одновременно когда две соседние параболы её полностью накрывают. Всего событий <tex>S_iO(n)</tex> и (<tex>S_jn</tex>- число вершин). При рассмотрении трёх сайтов <tex>S_i</tex>Для каждого события вычисляется его время (позиция заметающей прямой), события кладутся в очередь с приоритетом (отсюда <tex>S_jO(\log n)</tex> по времени) и <tex>S_k</tex>обрабатываются, окружность, касающаяся всех трёх сайтов, называется '''тритангентной окружностью Вороного''' пока очередь непуста. При обработке событий также записываются пары взаимодействующих вершин (''tritangent Voronoi circle''у которых сайты имеют общую границу). Точки, принадлежащие рёбрам Вороного, являются центрами битангентных окружностей, а вершины {{---}} тритангентныхэто и является результатом работы алгоритма.

Рассмотрим <tex>S \notin \Sigma_I</tex>. Будем говорить, что <tex>S</tex> '''конфликтует''' с окружностью Вороного Сложность работы алгоритма - <tex>C</tex>, если <tex>S</tex> пересекается с кругом, ограниченным <tex>C</tex>. Также <tex>S</tex> конфликтует с ребром <tex>e \in V(S, \Sigma)</tex>, если он пересекается с кругом, ограниченным одной из окружностей Вороного с центром в точке, принадлежащей <tex>e</tex>. '''Область конфликтов''' O(''conflict region'') <tex>R_n \Sigma(Slog n)</tex> {{---}} множество точек 1-каркаса по времени и <tex>V_1O(\Sigman)</tex>, соответствующих окружностям Вороного, которые конфликтуют с <tex>S</tex>по памяти.

Более подробно:* [https://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.2011/Fortune.pdf Презентация с описанием в деталях] ===АлгоритмЧана ===Вершины проецируются из двумерной плоскости на поверхность параболоида (<tex>x, y</tex> остаются те же, добавляется <tex>z = x^2 + y^2</tex>). Далее по ним строится нижняя [[Статические_выпуклые_оболочки:_Джарвис,_Грэхем,_Эндрю,_Чен,_QuickHull|выпуклая оболочка]]. Поскольку параболоид выпуклый, никакие вершины не будут удалены. На выходе получаются рёбра между вершинами, которые соответствуют триангуляции Делоне. Сложность работы - <tex>O(n \log n)</tex>. ==Диаграмма k-го порядка =={{ОпределениеРассмотрим сначала алгоритм для слабо пересекающихся |definition='''Ячейка Вороного''' <tex>k</tex>'''-го порядка''' (<tex>\mathcal{V}_k(p_1, p_2, ..., p_k)</tex>) — множество точек, имеющих в качестве ближайших <tex>k</tex> соседей множество сайтов<tex>p_1, p_2, ..., а потом обобщим его для случая сильно пересекающихся сайтовp_k</tex>.}}

===Случай слабо пересекающихся сайтов===Пусть мы уже построили Чтобы построить диаграмму <tex>k</tex>-го порядка, возьмём диаграмму Вороного <tex>k - 1</tex>-го порядка. Каждая ячейка построена для некоторого множества набора <tex>k-1</tex> сайтов. Обозначим множество этих сайтов за <tex>S</tex>. [[Пересечение выпуклых многоугольников|Пересечём]] каждую из этих ячеек с ячейками диаграммы первого порядка, построенной на множестве сайтов <tex>P \Sigmasetminus S</tex>. Рассмотрим процедуру вставки нового сайта Когда мы пересекаем ячейку <tex>k-1</tex>-го порядка для точек <tex>S</tex> с ячейкой первого порядка для точки <tex>p_i</tex>, получаем ячейку для множества <tex>S\cup \{p_i\}</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 \cdot n^3)</tex>.

'''1'''{||[[Файл: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>Sn - 1</tex> с каркасом <tex>V_1-го порядка (\Sigmaона же farthest-point диаграмма)</tex>.для данного набора сайтов]]|}

== Farthest-point диаграмма =={{Определение|definition=Диаграмма <tex>n - 1</tex>-го порядка является '''2farthest-point диаграммой''', т. Найти всю область конфликтов е. в каждой её ячейке все точки являются наиболее удалёнными от какого-то сайта <tex>S</tex> c каркасом <tex>V_1(\Sigma)</tex>.}}

'''3'''. Построить диаграмму Вороного для === Свойства ==={{Лемма|statement=Для любой точки <tex>q</tex> плоскости самый удалённый от неё сайт из <tex>P</tex> должен лежать на [[Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull|выпуклой оболочке]] <tex>\Sigma \cup \{S\} P</tex>.|proof=[[Файл:voronoi-farthest-inside.png|200px|right]]Сайт, не находящийся на выпуклой оболочке, лежит внутри неё по свойствам выпуклой оболочки.

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

Пусть сайт <tex>S</tex> {{Лемма|statement=Каждый сайт, который является вершиной выпуклой оболочки сайтов, имеет ячейку в farthest---}} это точка <tex>p</tex>point диаграмме.|proof=Докажем по индукции.

{{Теорема|statement=Пусть <tex>\Sigma</tex> {{---}} множество слабо пересекающихся База индукции: для двух сайтов, <tex>p</tex> {{---}} точка, <tex>p \notin \Sigma</tex>. Тогда <tex>\partial R_\Sigma(p)</tex> {{--они оба являются вершинами выпуклой оболочки и оба имеют ячейку в farthest-}} связная кривая, содержащая более одной точки.|proof=Пусть <tex>C = V(p, \Sigma \cup \{p\})</tex>, <tex>R_\Sigmapoint диаграмме (pдальняя от сайта полуплоскость) = \varepsilon</tex>.

Заметим, что Переход: добавим сайт <tex>\varepsilon = V_1(\Sigma) \cap Cp</tex>так, что он станет новой вершиной выпуклой оболочки. Пусть он не имеет ячейку в farthest-point диаграмме, то есть уже имеющаяся перед его добавлением диаграмма не меняется. Если бы область конфликтов <tex>\varepsilon</tex> была пустойДля построения farthest-point диаграммы проводятся серединные перпендикуляры между всеми парами сайтов, и полученные полуплоскости пересекаются; раз новой ячейки не добавилось, то было бы верно серединные перпендикуляры между <tex>C \subset V(q, \Sigma \cup \{p\})</tex> для некоторого <tex>q \in \Sigma</tex> и остальными сайтами совпали с уже имеющимися перпендикулярами. Это возможно, только если <tex>V(q, \Sigma \cup p)</tex> не было бы односвязнымсовпал с другим сайтом. Пришли к противоречию.}}

Пусть <tex>\varepsilon_1, \varepsilon_2{{Утверждение|statement=Сайт имеет ячейку в farthest-point диаграмме тогда и только тогда, когда он является вершиной выпуклой оболочки всех сайтов.|proof=Непосредственно следует из двух предыдущих лемм.. , \varepsilon_k</tex> {{---}} связные компоненты <tex>\varepsilon</tex> для некоторого <tex>k</tex>.

Предположим, что <tex>k \ge 2</tex>{{Утверждение|statement=Все ячейки в farthest-point диаграмме неограничены.|proof=[[Файл:voronoi-farthest-unbounded. Тогда cуществует путь png|200px|right]]Пусть <tex>P \subseteq C \setminus \varepsilonp_i</tex>— сайт на выпуклой оболочке сайтов, соединяющий две точки а <tex>x</tex> и <tex>y</tex> на границе <tex>C</tex> и отделяющий <tex>\varepsilon_1</tex> от <tex>\varepsilon_2q</tex>. <tex>P \cap \varepsilon = \emptyset \Rightarrow P \cap V_1^\circ(\Sigma) = \emptyset \Rightarrow P \subseteq V(s— точка, \Sigma)</tex> для некоторого <tex>s \in \Sigma</tex>которой он является наиболее удалённым. <tex>xТогда для всех точек на луче, y \in P \Rightarrowлежащем на </tex> все достаточно малые окрестности <tex>U(x)p_i q</tex>, <tex>U(y)</tex> полностью содержатся начинающемся в <tex>V(q, \Sigma)</tex>. Значит, точки пересечения этих окрестностей с дополнением и не проходящим через <tex>Cp_i</tex> лежат в <tex>V(q, \Sigma \cup p)сайт </tex> и могут быть соединены путём <tex>L \subseteq V(q, \Sigma \cup \{p\}) \subseteq V(q, \Sigma)p_i</tex>будет наиболее удалённым среди остальных сайтов. СледовательноЗначит, цикл ячейка сайта <tex>P \circ Lp_i</tex> полностью содержится в <tex>V(qfarthest-point диаграмме включает в себя этот луч, \Sigma)</tex> и содержит <tex>\varepsilon_1</tex> и <tex>\varepsilon_2</tex> в своей внутренности. Это противоречиеа значит, следовательно <tex>k = 1</tex>неограничена.

Первый шаг алгоритма начинается с поиска ближайшего соседа === Алгоритм ===Чтобы найти farthest-point диаграмму, сначала найдём выпуклую оболочку всех сайтов. Обозначим сайты, её образующие, через <tex>N_\Sigmap_1, p_2, ..., p_m</tex>. Запомним порядки обхода для каждой вершины выпуклой оболочки по часовой стрелке (p<tex>cw(p_i)</tex> точки p среди сайтов ) и против часовой (<tex>\Sigmaccw(p_i)</tex> ) и сделаем случайную перестановку точек. Далее удаляем из выпуклой оболочки все точки, кроме первых трёх (если есть несколько ближайшихзапоминая при этом их соседей в оболочке на момент удаления). После этого строим farthest-point диаграмму для первых трёх точек (пересекая полуплоскости) и последовательно добавляем остальные (удалённые) в порядке, то подойдёт любой из них)обратном порядку удаления. {||[[Файл:voronoi-farthest-construct. Либо png|600px|thumb|Построение очередной ячейки farthest-point диаграммы]]|} Для точки <tex>p_i</tex>N_\Sigmaячейка встанет «между» ячейками, соответствующими <tex>cw(pp_i)</tex> и <tex>pccw(p_i)</tex> {{---}} это одна и та же точка, и ничего делать не нужно, либо . Перед добавлением <tex>pp_i</tex> конфликтует хотя бы с одним ребром, принадлежащим границе ячейки <tex>Vcw(N_\Sigmap_i)</tex> и <tex>ccw(p)p_i)</tex>— соседи, поэтому между ними построен серединный перпендикуляр. Тогда первый шаг завершается рассмотрением границы Серединный перпендикуляр к <tex>Vp_i ccw(N_\Sigmap_i)</tex> даст новое ребро, которое лежит в farthest-point ячейке <tex>ccw(p)p_i)</tex> и возвращением одного из рёбер, конфликтующих с является частью границы ячейки <tex>pp_i</tex>. Как было сказано раньше, второй шаг {{---}} DFS по рёбрам Обойдём ячейку <tex>V_1ccw(\Sigmap_i)</tex> с целью найти все рёбрапо часовой стрелке, чтоб понять, конфликтующие с точкой какое ребро пересечёт перпендикуляр. С другой стороны этого ребра лежит ячейка какой-то точки <tex>pp_j</tex>. После того, как мы узнали и серединный перпендикуляр <tex>p_i p_j</tex>R_\Sigma(p)тоже даст ребро ячейке <tex>p_i</tex>, третий шаг . Аналогично совершим обход и так далее. Последний серединный перпендикуляр будет заключаться в создании новой ячейки Вороного, имеющей границу построен для <tex>R_\Sigmap_i cw(pp_i)</tex>.После этого удаляем рёбра, которые лежат внутри новой ячейки. == См. также ==* [[Трапецоидная карта]]* [[Триангуляция Делоне]]* [[Straight skeleton]] == Источники ==* de Berg, Cheong, van Kreveld, Overmars. Computational Geometry, Algorithms and Applicants, 2008. pp. 147-151, 164-166* [http://students.info.uaic.ro/~emilian.necula/vor2.pdf Algorithms for constructing Voronoi diagrams, Vera Sacrist´an {{---}} Incremental algorithm]* [http://en.wikipedia.org/wiki/Voronoi_diagram Wikipedia — Voronoi diagram]* [https://web.archive.org/web/20170329014016/http://www.cs.uu.nl/docs/vakken/ga/slides7b.pdf Computational Geometry {{---}} Lecture 13: More on Voronoi diagrams]