418
правок
Изменения
Определение, немного свойств
{{В разработке}}
== Определения ==
=== Неформальное определение ===
[[Файл:voronoi-diagram.png|200px|thumb|right|Пример диаграмы Вороного]]
Есть множество точек <tex>P</tex> на плоскости. Для всех точек <tex>q \notin P</tex> этой плоскости узнаем ближайшую к <tex>q</tex> точку из <tex>P</tex>. Таким образом получим разбиение плоскости на кусочки, в каждом из которых содержится одна точка <tex>p_i</tex> из <tex>P</tex> и все точки <tex>q</tex>, для которых <tex>p_i</tex> — ближайшая среди точек из <tex>P</tex>.
=== Формальное определение ===
<tex>P = \{ p_1, p_2, ..., p_n\}</tex> — множество точек на плоскости. Назовём их '''сайтами''' (''site'').
{{Определение
|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 \in h(p, q)</tex> тогда и только тогда, когда <tex>\rho(r, p) < \rho(r, q)</tex>. Отсюда вытекает следующее:
{{Утверждение
|statement=<tex>\mathcal{V}(p_i) = \cap_{1 \leqslant j \leqslant n, j \neq i} h(p_i, p_j)</tex>
}}
==Обозначения и определения==
'''Сайт''' (''site'') {{---}} общее название для точки <tex>p</tex> или замкнутого отрезка <tex>t</tex>.
