Изменения

[[Файл:voronoi-diagram.png|200px|thumb|right|Пример диаграммы Вороного]]Есть множество точек <tex>P</tex> на плоскости. Для всех Кусочек плоскости из точек <tex>q \notin P</tex> этой плоскости узнаем ближайшую к такой, что для всех <tex>q</tex> точку ближайшей точкой из множества <tex>P</tex>. Таким образом получим разбиение плоскости на кусочки, в каждом из которых содержится является одна и та же точка <tex>p_ip</tex> из <tex>P</tex> и все , называется ячейкой Вороного точки <tex>qp</tex>, . Разбиение плоскости на такие ячейки для которых всех точек <tex>p_i\in P</tex> — ближайшая среди точек из называется диаграммой Вороного для множества <tex>P</tex>.

<tex>P = \{ p_1, p_2, ..., p_n\}</tex> — множество точек на плоскости. Назовём их '''сайтами''' (''site'').

|definition='''Диаграмма Вороного''' (''Voronoi diagram'', <tex>Vor(p_i \in P)</tex>) для сайтов <tex>P = \{ p_1, p_2, ..., p_n\}</tex> на плоскости — это разбиение плоскости на <tex>n</tex> ячеек (называется '''ячейка Вороногосайтом''', (''Voronoi cellsite'', <tex>\mathcal{V}(p_i)</tex>), по одной для каждого сайта, которые обладают свойством: <tex>\rho(q, p_i) < \rho(q, p_j)</tex> для всех <tex>p_j \in P, \ j \neq i</tex>.

{{Определение|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='''Диаграмма Вороного''' (''Voronoi 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>. Отсюда вытекает следующее:

|statement=<tex>\mathcal{V}(p_i) = \cap_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> рёбрами.

=== Отсутствие прямых в общем случае Топология диаграммы Вороного ===

|proof=[[Файл:voronoi-not-lines.png|200px|thumb|right]] В случае, если все сайты лежат на одной прямой, каждая пара соседних сайтов порождает серединный перпендикуляр к отрезку, содержащему их, и, соответственно, к прямой, которая содержит все сайты. Так получаются <tex>n - 1</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]]

=== Линейность Размер структуры ===

|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_v_\infty</tex>, и все полубесконечные рёбра мы превратим в рёбра, инцидентные ей. Таким образом мы увеличили число вершин на одну, а число рёбер не изменилось. Число граней равно <tex>n</tex> по определению диаграммы Вороного. Тогда по формуле Эйлера получаем <tex>(v + 1) - e + n = 2</tex>.Сумма степеней всех вершин полученного графа равна <tex>2e</tex>, так как у каждого ребра есть ровно два конца (нет петель). Также у из каждой вершины исходят как минимум три ребра. Отсюда получаем <tex>2e \geqslant 3 (n v + 1)</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>.

|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> одновременно, то есть вершиной диаграммудиаграммы.

|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>, (так как <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> является ребром триангуляции Делоне. За счёт равносильности в обеих используемых леммах мы добавим все рёбра и не построим лишних.

Будем [[Пересечение полуплоскостей, связь с выпуклыми оболочками|пересекать полуплоскости по ]] по [[#intersect|свойству ячейки диаграммы]]. Необходимо <tex>n</tex> раз для каждого сайта пересечь <tex>n - 1</tex> плоскость, что суммарно делается за <tex>O(n^2 \log n)</tex>.

==Обозначения и определения= Инкрементальный алгоритм ==='''Сайт''' Храним диаграмму в [[ППЛГ и РСДС (''site''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>p\mathcal{V}(p_k)</tex> или замкнутого отрезка ; на следующем шаге будем строить серединный перпендикуляр для <tex>tp_{i+1} p_k</tex>и так далее.

В процессе построения перпендикуляров необходимо обновлять РСДС. Каждый раз, когда новое полуребро <tex>t^\circe</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}(i+1)</tex>, справа — <tex>\mathcal{V}(''strongly intersect''j)</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>x \in \mathbb{E}^2O(i)</tex> до замкнутого сайта , значит, суммарно диаграмма из <tex>S_in</tex>: сайтов с нуля создаётся за <tex>\deltaO(x, S_in^2) = \min{\{||x - y|| : y \in S_i\}}</tex>.

Пусть <tex>H_{ij} = \{x \in \mathbb{E}^2 ||[[Файл:voronoi-incremental-zero-step.png|200px|thumb|Локализация]]|[[Файл: \delta(x, S_i) \le \delta(x, S_j)\}</tex>voronoi-incremental-first-step. '''Ячейка Вороного''' (''Voronoi cell'') <tex>V(S_i, \Sigma)</tex> {{png|200px|thumb|Добавление первого ребра]]|[[Файл:voronoi-incremental.png|200px|thumb|Добавление третьего ребра]]|[[Файл:voronoi-update-dcel.png|400px|thumb|Обновление структуры при добавлении ребра]]|}} множество точек, которые находятся ближе к <tex>S_i</tex>, чем к любому другому сайту, то есть <tex>V(S_i, \Sigma) = \cap_{i \ne j}H_{ij}</tex>.

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

'''Вершина Вороного''' Сложность работы алгоритма - <tex>O(n \log n)</tex> по времени и <tex>O(''Voronoi vertex''n) {{---}} точка, которая принадлежит хотя бы трём ячейкам Вороного</tex> по памяти.

'''Диаграмма Вороного''' (''Voronoi diagram'') <tex>V(\Sigma)<Более подробно:* [https:/tex> множества сайтов <tex>\Sigma</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.2011/Fortune.pdf Презентация с описанием в деталях]

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

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

Пусть сайты Чтобы построить диаграмму <tex>S_ik</tex> и -го порядка, возьмём диаграмму <tex>S_jk - 1</tex> слабо пересекаются-го порядка. Тогда '''битангентная окружность Вороного''' (''bitangent Voronoi circle'') Каждая ячейка построена для некоторого набора <tex>C_{ij}k-1</tex> {{---}} окружность, касающаяся одновременно сайтов. Обозначим множество этих сайтов за <tex>S_iS</tex> и . [[Пересечение выпуклых многоугольников|Пересечём]] каждую из этих ячеек с ячейками диаграммы первого порядка, построенной на множестве сайтов <tex>S_jP \setminus S</tex>. При рассмотрении трёх сайтов Когда мы пересекаем ячейку <tex>S_ik-1</tex>, -го порядка для точек <tex>S_jS</tex> и с ячейкой первого порядка для точки <tex>S_kp_i</tex>, окружностьполучаем ячейку для множества <tex>S \cup \{p_i\}</tex>. После пересечения ячеек необходимо объединить те, касающаяся всех трёх которые отвечают за одинаковый набор сайтов, называется '''тритангентной окружностью Вороного''' (''tritangent Voronoi circle''это могут быть только соседние по ребру ячейки). Точки, принадлежащие рёбрам Вороного, являются центрами битангентных окружностей, а вершины {{---}} тритангентных.

Рассмотрим Итого совершаем <tex>S \notin \Sigma_Ik</tex>. Будем говоритьшагов, что на каждом строим <tex>SO(n)</tex> '''конфликтует''' с окружностью диграмм Вороного за время <tex>CO(n^3)</tex>, если пересекаем <tex>SO(n)</tex> пересекается ячеек с кругом, ограниченным <tex>CO(n)</tex>. Также ячейками за <tex>S</tex> конфликтует с ребром <tex>e \in VO(S, \Sigman)</tex>времени, если он пересекается с кругом, ограниченным одной из окружностей Вороного с центром в точке, принадлежащей а потом объединяем ячейки за <tex>eO(n)</tex>. '''Область конфликтов''' (''conflict region'') линейное количество соседних рёбер ячейки, а объединение происходит за <tex>R_\SigmaO(S1)</tex> {{---}} множество точек 1-каркаса за счёт структуры РСДС). Итого <tex>V_1O(k \Sigmacdot n^3)</tex>, соответствующих окружностям Вороного, которые конфликтуют с <tex>S</tex>.

==Алгоритм=={|Рассмотрим сначала алгоритм |[[Файл: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 диаграмма) для слабо пересекающихся данного набора сайтов, а потом обобщим его для случая сильно пересекающихся сайтов.]]|}

===Случай слабо пересекающихся сайтовFarthest-point диаграмма =={{Определение|definition=Пусть мы уже построили диаграмму Вороного для некоторого множества Диаграмма <tex>\Sigman - 1</tex>-го порядка является '''farthest-point диаграммой''', т. Рассмотрим процедуру вставки нового е. в каждой её ячейке все точки являются наиболее удалёнными от какого-то сайта <tex>S</tex>.}}

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

'''1'''. Найти первый конфликт сайта Пусть самый удалённый от точки <tex>Sq</tex> с каркасом сайт <tex>V_1(\Sigma)p_i</tex>не лежит на выпуклой оболочке (т.е. '''2'''лежит внутри неё). Найти всю область конфликтов сайта Проведём луч <tex>Sq p_i</tex> c каркасом . Он пересечёт ребро выпуклой оболочки <tex>V_1(\Sigma)p_j p_k</tex>. '''3'''Получатся два смежных угла, рассмотрим тот, который оказался прямым или тупым. Построить диаграмму Вороного для Тогда в полученном треугольнике <tex>\Sigma rho(q, p_j) > \cup \{S\} rho(q, p_i)</tex>, так как напротив большего угла лежит большая сторона. Пришли к противоречию. '''4'''. Обновить локализационную структуру.}}

|statement=<tex>\Sigma</tex> {{---}} слабо пересекающееся между собой множество Сайт, который лежит внутри выпуклой оболочки сайтов. Тогда <tex>\forall s \in \Sigma</tex> ячейки Вороного <tex>V(s, \Sigma)</tex> {{--не может иметь ячейку в farthest-}} односвязные множестваpoint диаграмме.|proof=Для начала докажем, что ячейки связны. Пусть это не так и у ячейки <tex>V(s, \Sigma)</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>farthest-point диаграмме. Значит существует путь от <tex>p</tex> до <tex>s'</tex>, который короче, чем <tex>P</tex>, следовательно и <tex>\delta(p, s') < \delta(p, s) = |P|</tex>. Противоречие. Теперь допустим, что <tex>V(s, \Sigma)</tex> содержит разрыв в виде другой ячейки Тогда внутри неё есть точка <tex>V(s', \Sigma)q</tex>. Проведём прямую, которая соответствует кратчайшему расстоянию между Но по предыдущей лемме самый удалённый для <tex>sq</tex> и <tex>s'</tex> и рассмотрим точку <tex>p</tex>, которая сайт лежит на её продолжении за <tex>s'</tex> и принадлежит <tex>V(sвыпуклой оболочке, \Sigma)</tex>. Такая точка будет существоватьа значит, т.к. <tex>V(s', \Sigma)</tex> лежит внутри <tex>V(s, \Sigma)</tex>. Получаем, что кратчайший путь от сайт <tex>p</tex> до не может быть самым удалённым для <tex>s</tex> проходит через <tex>s'q</tex>. Опять противоречиеПришли к противоречию.

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

Заметим, что <tex>\varepsilon = 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оба имеют ячейку в farthest-point диаграмме (q, \Sigma \cup sдальняя от сайта полуплоскость)</tex> не было бы односвязным.

Пусть Переход: добавим сайт <tex>\varepsilon_1, \varepsilon_2, ... , \varepsilon_kp</tex> {{так, что он станет новой вершиной выпуклой оболочки. Пусть он не имеет ячейку в farthest-point диаграмме, то есть уже имеющаяся перед его добавлением диаграмма не меняется. Для построения farthest--}} связные компоненты point диаграммы проводятся серединные перпендикуляры между всеми парами сайтов, и полученные полуплоскости пересекаются; раз новой ячейки не добавилось, то серединные перпендикуляры между <tex>\varepsilonp</tex> для некоторого и остальными сайтами совпали с уже имеющимися перпендикулярами. Это возможно, только если <tex>kp</tex>совпал с другим сайтом.Пришли к противоречию.}}

Предположим, что <tex>k \ge 2</tex>. Тогда cуществует путь <tex>P \subseteq C \setminus \varepsilon</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) {{Утверждение|statement= \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(q, \Sigma)</tex>. Значит, точки пересечения этих окрестностей с дополнением <tex>C</tex> лежат в <tex>V(q, \Sigma \cup s)</tex> farthest-point диаграмме тогда и могут быть соединены путём <tex>L \subseteq V(qтолько тогда, \Sigma \cup \{s\}) \subseteq V(q, \Sigma)</tex>. Следовательно, цикл <tex>P \circ L</tex> полностью содержится в <tex>V(q, \Sigma)</tex> и содержит <tex>\varepsilon_1</tex> или <tex>\varepsilon_2</tex> в своей внутренней частикогда он является вершиной выпуклой оболочки всех сайтов. Это противоречит тому, что <tex>V(q, \Sigma)</tex> {{---}} односвязное множество, следовательно <tex>k |proof= 1</tex>Непосредственно следует из двух предыдущих лемм.

Таким образом, для нахождения области конфликтов, можно найти одно конфликтующее ребро, а затем, при помощи DFS, найти все остальные. Пусть сайт <tex>S</tex> {{Утверждение|statement=Все ячейки в farthest-point диаграмме неограничены.|proof=[[Файл:voronoi-farthest-}} это точка <tex>p</tex>unbounded. Первый шаг алгоритма начинается с поиска ближайшего соседа png|200px|right]]Пусть <tex>N_\Sigma(p)p_i</tex> точки p среди — сайт на выпуклой оболочке сайтов , а <tex>\Sigmaq</tex> (если есть несколько ближайших— точка, то подойдёт любой из них)для которой он является наиболее удалённым. Будем хранить нашу диаграмму в скип-листе Тогда для тоговсех точек на луче, чтобы можно было быстро выполнять эти запросы. Либо лежащем на <tex>N_\Sigma(p)p_i q</tex> и , начинающемся в <tex>pq</tex> {{---}} это одна и та же точка, и ничего делать не нужно, либо проходящим через <tex>pp_i</tex> конфликтует хотя бы с одним ребром, принадлежащим границе ячейки сайт <tex>V(N_\Sigma(p))p_i</tex>будет наиболее удалённым среди остальных сайтов. Тогда первый шаг завершается рассмотрением границы <tex>V(N_\Sigma(p))</tex> и возвращением одного из рёберЗначит, конфликтующих с ячейка сайта <tex>pp_i</tex>. Как было сказано раньше, второй шаг {{в farthest---}} DFS по рёбрам <tex>V_1(\Sigma)</tex> с целью найти все рёбра, конфликтующие с точкой <tex>p</tex>. Теперьpoint диаграмме включает в себя этот луч, зная <tex>R_\Sigma(p)</tex>, можно создать новую ячейку Вороного <tex>V(S, \Sigma \cup \{S\})</tex> (а как это сделатьзначит, я не очень понимаю)неограничена. Если же <tex>S</tex> {{---}} это замкнутый отрезок <tex>t</tex>, то сначала вставляем конечные точки <tex>p'_t</tex> и <tex>p''_t</tex>, используя процедуру, описанную выше. Остаётся вставить открытый отрезок <tex>t^\circ</tex>. Так как <tex>p'_t</tex> и <tex>p''_t</tex> {{---}} соседи <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>p</tex> {{Чтобы найти farthest---}} точкаpoint диаграмму, сначала найдём выпуклую оболочку всех сайтов. Обозначим сайты, её образующие, которая сильно пересекается с отрезком через <tex>t_i</tex>p_1, p_2, т.е. <tex>p \in t^\circ</tex>. Понятно, что <tex>t^\circ</tex> будет ближайшим соседом <tex>p</tex> в <tex>\Sigmap_m</tex>. Пусть Запомним порядки обхода для каждой вершины выпуклой оболочки по часовой стрелке (<tex>e'_icw(pp_i)</tex> ) и против часовой (<tex>e''_iccw(pp_i)</tex> {{---}} два ребра <tex>V(t^\circ, \Sigma)</tex>, которые пересекаются с нормалями к <tex>t</tex>, проведёнными и сделаем случайную перестановку точек. Далее удаляем из выпуклой оболочки все точки <tex>p</tex> , кроме первых трёх (см. рисунокзапоминая при этом их соседей в оболочке на момент удаления). Пусть <tex>v'_i(p)</tex> и <tex>v''_i(p)</tex> {{После этого строим farthest---}} точки пересечения нормалей с рёбрами <tex>e'_ipoint диаграмму для первых трёх точек (pпересекая полуплоскости)</tex> и <tex>e''_iпоследовательно добавляем остальные (pудалённые)</tex> соответственнов порядке, обратном порядку удаления. Тогда алгоритм вставки точки <tex>p</tex> в диаграмму <tex>V(\Sigma)</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_intersectvoronoi-farthest-construct.png|300px600px|thumb|rightПостроение очередной ячейки farthest-point диаграммы]]

Если же мы хотим вставить в диаграмму отрезок Для точки <tex>tp_i</tex>ячейка встанет «между» ячейками, то вставляем сначала его крайние точки соответствующими <tex>p'_tcw(p_i)</tex> и <tex>p''_tccw(p_i)</tex>. Затем, начиная с Перед добавлением <tex>p'_tp_i</tex>, ищем первый конфликт <tex>t^\circcw(p_i)</tex> с текущей диаграммой Вороного и ищем всю область конфликтов. Во время этого поиска, прежде чем тестировать ребро Вороного <tex>e</tex> существующей диаграммы на потенциальный конфликт, мы проверяем, не пересекается ли <tex>t^\circccw(p_i)</tex> с одним из сайтов— соседи, связанных с <tex>e</tex>поэтому между ними построен серединный перпендикуляр. Если такой сайт Серединный перпендикуляр к <tex>S_ip_i ccw(p_i)</tex> найдендаст новое ребро, то поиск останавливается. Если <tex>S_i</tex> {{--которое лежит в farthest-}} точка, point ячейке <tex>ccw(p_i</tex>, то вставляем отрезки <tex>p'_tp_i)</tex> и является частью границы ячейки <tex>p_ip''_tp_i</tex> рекурсивно. Если Обойдём ячейку <tex>S_iccw(p_i)</tex> {{-по часовой стрелке, чтоб понять, какое ребро пересечёт перпендикуляр. С другой стороны этого ребра лежит ячейка какой--}} отрезок <tex>t^\circ_i</tex>, то сначала проверяем, не принадлежит ли один из точки <tex>t^\circp_j</tex>, <tex>t^\circ_i</tex> другому. Если так и есть, то прекращаем работу, иначе вычисляем точку пересечения серединный перпендикуляр <tex>p_+p_i p_j</tex> отрезков тоже даст ребро ячейке <tex>t^\circp_i</tex> . Аналогично совершим обход и так далее. Последний серединный перпендикуляр будет построен для <tex>t^\circ_ip_i cw(p_i)</tex>. После этого удаляем рёбра, вставляем её в диаграмму, а затем рекурсивно вставляем отрезки <tex>p'_tp_+</tex> и <tex>p_+p''_t</tex>которые лежат внутри новой ячейки.

Время работы данного алгоритма составляет <tex>O((n + m)\log^2m)</tex>, где <tex>n</tex> {{---}} количество элементов во входном множестве <tex>\Sigma_I</tex>, а <tex>m</tex> {{---}} количество пар сильно пересекающихся сайтов== См.также ==* [[Трапецоидная карта]]* [[Триангуляция Делоне]]* [[Straight skeleton]]

==СсылкиИсточники ==* de Berg, Cheong, van Kreveld, Overmars. Computational Geometry, Algorithms and Applicants, 2008. pp. 147-151, 164-166* [http://citeseerxstudents.istinfo.psuuaic.eduro/viewdoc~emilian.necula/download?doi=10vor2.1pdf Algorithms for constructing Voronoi diagrams, Vera Sacrist´an {{---}} Incremental algorithm]* [http://en.1wikipedia.112.8990&rep=rep1&type=pdf ''Menalaos I. Karavelas'' A robust and efficient implementation for the segment org/wiki/Voronoi_diagram Wikipedia — Voronoi diagram.]* [https://web.archive.org/web/20170329014016/http://www.sciencedirectcs.comuu.nl/sciencedocs/articlevakken/pii/0925772193900333ga/slides7b.pdf?md5=ce44776db4922c6579a191a7c7ada933&pid=1Computational Geometry {{-s2.0-0925772193900333-main.pdf ''Rolf Klein'' Randomized incremental construction of abstract }} Lecture 13: More on Voronoi diagrams.]