Изменения
→Алгоритм Чана
=== Неформальное определение ===
=== Формальное определение ===
<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> рёбрами.
=== Отсутствие прямых в общем случае Топология диаграммы Вороного ===
{{Теорема
|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|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>.
Домножим равенство на два и вычтем из него полученную нижнюю границу для <tex>2 \cdot e</tex>, в результате получим <tex> v \leqslant 2n - 5</tex>. Далее подставим этот результат в равенство и получим <tex>e \leqslant 3n - 6</tex>, что и требовалось доказать.
}}
=== Связь с триангуляцией Делоне ===
{{Определение
|definition='''Наибольшая пустая окружность ''' точки <tex>q</tex> по отношению к <tex>P</tex> (''largest empty circle of ''<tex>q</tex>'' with respect to ''<tex>P</tex>, <tex>C_P(q)</tex>) — наибольшая окружность с центром в <tex>q</tex> такая, что во внутренности соответствующего ей круга не лежит ни одного сайта из <tex>P</tex>.
}}
{{Лемма
|statement=Точка <tex>q</tex> — вершина диаграммы Вороного в том и только в том случае, когда <tex>C_P(q)</tex> содержит три и более сайтов на своей границе.
|proof=Предположим, что <tex>q</tex> существует, а <tex>p_i, \ p_j, \ p_k</tex> — соответствующие точки. Так как внутри <tex>C_P(q)</tex> нет других сайтов, а <tex>q</tex> равноудалена от точек <tex>p_i, \ p_j, \ p_k</tex>, <tex>q</tex> должна быть на границе <tex>\mathcal{V}(p_i), \ \mathcal{V}(p_j), \ \mathcal{V}(p_k)</tex> одновременно, то есть вершиной диаграммудиаграммы.
Докажем в другую сторону: каждая вершина <tex>q</tex> диаграммы инцидентна минимум трём рёбрам, и, поэтому, как минимум трём ячейкам <tex>\mathcal{V}(p_i), \ \mathcal{V}(p_j), \ \mathcal{V}(p_k)</tex>. Тогда <tex>q</tex> лежит на равном расстоянии от <tex>p_i, \ p_j, \ p_k</tex> и не может быть другого сайта ближе к <tex>q</tex>, так как иначе <tex>\mathcal{V}(p_i), \ \mathcal{V}(p_j), \ \mathcal{V}(p_k)</tex> не сойдутся в <tex>q</tex>. Поэтому можно построить окружность с центром в <tex>q</tex> и <tex>p_i, \ p_j, \ p_k</tex> на границе так, что внутри не будет других сайтов.
}}
{{Лемма
|statement=Серединный перпендикуляр к отрезку <tex>p_i p_j</tex> образует ребро диаграммы Вороного в том и только в том случае, если на нём есть точка <tex>q</tex> такая, что <tex>C_P(q)</tex> содержит на своей границе только сайты <tex>p_i, \ p_j</tex>.
|proof=[[Файл:voronoi-circles.png|200px|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> и так далее.
{{Лемма
|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%"|Пусть <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> будет выглядеть следующим образом:
|}
==СсылкиИсточники ==* 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.]
[[Категория: Вычислительная геометрия]]
[[Категория: Триангуляция Делоне и диаграмма Вороного]]