Изменения

[[Файл: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> — множество точек на плоскости. Назовём их  {{Определение|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='''Диаграмма Вороного''' (''Voronoi diagram'', <tex>Vor(P)</tex>) для сайтов <tex>P = \{ p_1, p_2, ..., p_n\}</tex> на плоскости — это разбиение плоскости на <tex>n</tex> ячеек ('''ячейка ячейки Вороного''', ''Voronoi cell'', <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>.

В зависимости от контекста будем называть диаграммой Вороного как разбиение на ячейки, так и составляющие [[Основные определения теории графов|граф]] из вершин и рёбер, составляющих эти ячейки вершины и рёбра.

=== Количество вершин и рёбер в ячейке Связь с пересечением полуплоскостей ===Возьмём две точки плоскости: <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) = \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> является ребром триангуляции Делоне. За счёт равносильности в обеих используемых леммах мы добавим все рёбра и не построим лишних.

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

=== Инкрементальный алгоритм ===Храним диаграмму в [[ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых|РСДС]]. Пусть у нас уже есть диаграмма для точек <tex>t^\circp_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> и так далее.

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

Расстояние от точки * создаём вершину <tex>v</tex> с полуребром <tex>e</tex>;* для полуребра <tex>e</tex> в РСДС второй конец в вершине <tex>v</tex>, следующее полуребро — <tex>e'</tex>, инцидентные грани — слева <tex>x \in mathcal{V}(i+1)</tex>, справа — <tex>\mathbbmathcal{EV}^2(j)</tex> до замкнутого сайта ;* добавляем в РСДС полуребро <tex>S_ie + 1</tex>: с началом в <tex>\delta(xv</tex> и предыдущим полуребром <tex>e</tex>;* удаляем все полурёбра, лежащие между вершиной начала <tex>e</tex> и вершиной конца <tex>e</tex>, по часовой стрелке;* обновляем полуребро, S_i) = \min{соответствующее грани для <tex>\mathcal{||x - y|| : y \in S_i\}V}(p_j)</tex> — им становится <tex>e</tex>.

Пусть Каждый шаг выполняется за <tex>H_{ij} = \{x \in \mathbb{E}^2 : \deltaO(x, S_i) \le \delta(x, S_ji)\}</tex>. '''Ячейка Вороного''' (''Voronoi cell'') <tex>V(S_i, \Sigma)</tex> {{---}} множество точекзначит, которые находятся ближе к суммарно диаграмма из <tex>S_in</tex>, чем к любому другому сайту, то есть сайтов с нуля создаётся за <tex>VO(S_i, \Sigman^2) = \cap_{i \ne j}H_{ij}</tex>.

'''Ребро Вороного''' (''Voronoi edge'') {{||[[Файл:voronoi-incremental-zero-step.png|200px|thumb|Локализация]]|[[Файл:voronoi-incremental-first-step.png|200px|thumb|Добавление первого ребра]]|[[Файл:voronoi-incremental.png|200px|thumb|Добавление третьего ребра]]|[[Файл:voronoi-update-dcel.png|400px|thumb|Обновление структуры при добавлении ребра]]|}} связное множество точек, принадлежащих пересечению ровно двух ячеек Вороного.

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

'''Диаграмма Вороного''' (''Voronoi diagram'') Сложность работы алгоритма - <tex>VO(n \Sigmalog n)</tex> множества сайтов по времени и <tex>\SigmaO(n)</tex> {{---}} разбиение плоскости на вершины, рёбра и ячейки Вороногопо памяти.

'''1-каркас''' (''1-skeleton'') <tex>V_1(\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.2011/Fortune.pdf Презентация с описанием в деталях]

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

Пусть сайты <tex>S_i</tex> и == Диаграмма k-го порядка =={{Определение|definition='''Ячейка Вороного''' <tex>S_jk</tex> слабо пересекаются. Тогда '''битангентная окружность Вороного-го порядка''' (''bitangent Voronoi circle'') <tex>C_\mathcal{ijV}_k(p_1, p_2, ..., p_k)</tex> {{---}} окружность) — множество точек, касающаяся одновременно имеющих в качестве ближайших <tex>S_ik</tex> и соседей множество сайтов <tex>S_j</tex>p_1, p_2, ... При рассмотрении трёх сайтов <tex>S_i</tex>, <tex>S_j</tex> и <tex>S_kp_k</tex>, окружность, касающаяся всех трёх сайтов, называется '''тритангентной окружностью Вороного''' (''tritangent Voronoi circle''). Точки, принадлежащие рёбрам Вороного, являются центрами битангентных окружностей, а вершины {{---}} тритангентных.

Рассмотрим Чтобы построить диаграмму <tex>S \notin \Sigma_Ik</tex>. Будем говорить-го порядка, что возьмём диаграмму <tex>Sk - 1</tex> '''конфликтует''' с окружностью Вороного -го порядка. Каждая ячейка построена для некоторого набора <tex>Ck-1</tex>, если сайтов. Обозначим множество этих сайтов за <tex>S</tex> пересекается . [[Пересечение выпуклых многоугольников|Пересечём]] каждую из этих ячеек с кругомячейками диаграммы первого порядка, ограниченным построенной на множестве сайтов <tex>CP \setminus S</tex>. Также Когда мы пересекаем ячейку <tex>Sk-1</tex> конфликтует с ребром -го порядка для точек <tex>e \in V(S, \Sigma)</tex>, если он пересекается с кругом, ограниченным одной из окружностей Вороного с центром в точке, принадлежащей ячейкой первого порядка для точки <tex>ep_i</tex>. '''Область конфликтов''' (''conflict region'') , получаем ячейку для множества <tex>R_S \cup \Sigma(S)</tex> {{---}p_i\} множество точек 1-каркаса <tex>V_1(\Sigma)</tex>, соответствующих окружностям Вороного. После пересечения ячеек необходимо объединить те, которые конфликтуют с <tex>S</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>.

===Случай слабо пересекающихся сайтов==={||[[Файл:voronoi-first-order.png|200px|thumb|Диаграмма первого порядка]]|[[Файл:voronoi-second-order.png|200px|thumb|Диаграмма второго порядка]]|[[Файл:voronoi-third-order.png|200px|thumb|Диаграмма третьего порядка]]Пусть мы уже построили диаграмму Вороного для некоторого множества <tex>\Sigma</tex>|[[Файл:voronoi-tenth-order. Рассмотрим процедуру вставки нового сайта png|200px|thumb|Диаграмма <tex>Sn - 1</tex>.-го порядка (она же farthest-point диаграмма) для данного набора сайтов]]|}

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

'''2'''. Найти всю область конфликтов сайта Пусть самый удалённый от точки <tex>Sq</tex> c каркасом сайт <tex>V_1p_i</tex> не лежит на выпуклой оболочке (\Sigmaт.е. лежит внутри неё). Проведём луч <tex>q p_i</tex>. Он пересечёт ребро выпуклой оболочки <tex>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.]