Изменения

Перейти к: навигация, поиск

Диаграмма Вороного

10 001 байт добавлено, 15:03, 20 января 2020
→‎Алгоритм Чана
{{В разработке}}== Определения ===== Совсем неформальное определение ===[[Файл:voronoi-diagram.png|200px|thumb|right|Пример диаграммы Вороного]]Пусть есть карта города, на которой точками обозначены почтовые отделения. Человек хочет отправить письмо, и он пойдёт на ближайшую почту. Ему интересно знать, какое отделение ближе, для любой точки города — необходимость отправить письмо может наступить неожиданно. Для этого он может взять карту и расчертить её на ячейки так, чтобы внутри каждой ячейки находилось только одно отделение, а для всех остальных точек ячейки именно эта почта была ближайшей. Полученная картинка и будет диаграммой Вороного для точек-почт.
== Определения ==
=== Неформальное определение ===
[[Файл: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>. Отсюда вытекает следующее:
{{Утверждение
|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> рёбрами.
=== Топология диаграммы Вороного ===
{{Теорема
|statement=Пусть <tex>P</tex> — множество из <tex>n</tex> сайтов. Если они все лежат на одной прямой, то <tex>Vor(P)</tex> представляет собой <tex>n - 1</tex> параллельную прямую. Иначе <tex>Vor(P)</tex> связная и все её рёбра — либо отрезки, либо лучи.
|proof=[[Файл:voronoi-not-lines.png|200px|thumb|right]] В случае, если все сайты лежат на одной прямой, каждая пара соседних сайтов порождает серединный перпендикуляр к отрезку, содержащему их, и, соответственно, к прямой, которая содержит все сайты. Так получаются <tex>n - 1</tex> прямая, каждая из которых перпендикулярна прямой, содержащей сайты, а значит, эти прямые параллельны.
Рассмотрим теперь случай, когда сайты не лежат на одной прямой. Покажем, что рёбра — это отрезки или лучи, от противного. Предположим, что есть ребро <tex>e</tex>, являющееся прямой. Пусть оно — граница ячеек <tex>\mathcal{V}(p_i)</tex> и <tex>\mathcal{V}(p_j)</tex>. Пусть точка <tex>p_k \in P</tex> не лежит на прямой <tex>p_i p_j</tex> (по условию такая точка существует). Тогда серединный перпендикуляр к <tex>p_j p_k</tex> не параллелен <tex>e</tex>, и, значит, он его пересекает. Но тогда та часть <tex>e</tex>, что лежит в <tex>h(p_k, p_j)</tex>, не может быть границей <tex>\mathcal{V}(p_j)</tex>, потому что она ближе к <tex>p_k</tex>, чем к <tex>p_j</tex>. Пришли к противоречию.
Докажем теперь, что диаграмма связна. Предположим, что это не так. Тогда на её рёбрах найдутся две точки <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}(''site''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>pq</tex> или замкнутого отрезка и <tex>tp_i, \ p_j, \ p_k</tex>на границе так, что внутри не будет других сайтов.}}
{{Лемма|statement=Серединный перпендикуляр к отрезку <tex>p_i p_j</tex> образует ребро диаграммы Вороного в том и только в том случае, если на нём есть точка <tex>q</tex> такая, что <tex>t^C_P(q)</tex> содержит на своей границе только сайты <tex>p_i, \circp_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> (''weakly intersect''так как <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> на границе, внутри которой не будет других сайтов. Триангуляции Делоне принадлежат [[Триангуляция Делоне#Критерий Делоне для рёбер|те и только те]] рёбра (''strongly intersect''с поправкой на точки, лежащие на одной окружности), если точка их пересечения принадлежит внутренности хотя бы одного из данных сайтовна которых можно построить такую окружность, что внутри неё не будет лежать никаких точек. Тогда ребро <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>.
'''Вершина Вороного''' (''Voronoi vertex'') {{---}} точка, которая принадлежит хотя бы трём ячейкам Вороного. Обновление РСДС происходит следующим образом:
* создаём вершину <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>\Sigmax, y</tex> остаются те же, добавляется <tex>z = x^2 + y^2</tex>). Далее по ним строится нижняя [[Статические_выпуклые_оболочки:_Джарвис,_Грэхем,_Эндрю,_Чен,_QuickHull|выпуклая оболочка]]. Поскольку параболоид выпуклый, никакие вершины не будут удалены. Рассмотрим процедуру вставки нового сайта На выходе получаются рёбра между вершинами, которые соответствуют триангуляции Делоне. Сложность работы - <tex>SO(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 \setminus S</tex>. Найти первый конфликт сайта Когда мы пересекаем ячейку <tex>k-1</tex>-го порядка для точек <tex>S</tex> с каркасом ячейкой первого порядка для точки <tex>p_i</tex>, получаем ячейку для множества <tex>V_1(S \cup \{p_i\Sigma)}</tex>. После пересечения ячеек необходимо объединить те, которые отвечают за одинаковый набор сайтов (это могут быть только соседние по ребру ячейки).
'''2'''. Найти всю область конфликтов сайта Итого совершаем <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>SO(1)</tex> c каркасом за счёт структуры РСДС). Итого <tex>V_1O(k \Sigmacdot n^3)</tex>.
'''3'''{||[[Файл: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>\Sigma \cup \{S\} n - 1</tex>.-го порядка (она же farthest-point диаграмма) для данного набора сайтов]]|}
== Farthest-point диаграмма =={{Определение|definition=Диаграмма <tex>n - 1</tex>-го порядка является '''4farthest-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>sq p_i</tex> и . Он пересечёт ребро выпуклой оболочки <tex>s'p_j p_k</tex> и . Получатся два смежных угла, рассмотрим точку <tex>p</tex>тот, которая лежит на её продолжении за который оказался прямым или тупым. Тогда в полученном треугольнике <tex>s'</tex> и принадлежит <tex>V\rho(sq, \Sigmap_j)</tex>. Такая точка будет существовать, т.к. <tex>V(s', \Sigma)</tex> лежит внутри <tex>Vrho(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>совпал с другим сайтом. Пришли к противоречию.
}}
|[[Файл:path.png|250px|thumb|right]]
|}
Таким образом{{Утверждение|statement=Сайт имеет ячейку в farthest-point диаграмме тогда и только тогда, для нахождения области конфликтов, можно найти одно конфликтующее ребро, а затем, при помощи DFS, найти все остальныекогда он является вершиной выпуклой оболочки всех сайтов.|proof=Непосредственно следует из двух предыдущих лемм.}}
Пусть сайт <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> с целью найти все рёбраpoint диаграмме включает в себя этот луч, конфликтующие с точкой <tex>p</tex>. Теперь, зная <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.]
[[Категория: Вычислительная геометрия]]
[[Категория: Триангуляция Делоне и диаграмма Вороного]]
Анонимный участник
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/46175...72199»

Навигация