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

Диаграмма Вороного конечного множества точек S на плоскости представляет такое разбиение плоскости, при котором каждая область этого разбиения образует множество точек, более близких к одному из элементов множества S, чем к любому другому элементу множества.

Диаграмма Вороного случайного множества точек на плоскости

Названа в честь Георгия Феодосьевича Вороного, который изучил общий n-мерный случай в 1908 году. Также известна как: мозаика Вороного, разбиение Вороного, разбиение Дирихле.

ИсторияПравить

Впервые применение подобных конструкций приписывают Декарту в 1644 году. Дирихле использовал двумерные и трехмерные диаграммы Вороного в своём труде о квадратичных формах в 1850.

СвойстваПравить

Имеет тесную связь и взаимно-однозначное соответствие с триангуляцией Делоне. А именно, если соединить рёбрами точки, области Вороного которых граничат друг с другом, полученный граф будет являться триангуляцией Делоне.

Алгоритмы построенияПравить

Простой алгоритмПравить

 

Диаграмма Вороного для двух точек. Полуплоскости $H_{pq}$$H_{{pq}}$  и $H_{qp}$$H_{{qp}}$  разделяются срединным перпендикуляром.

Рассмотрим серединный перпендикуляр отрезка, соединяющего некоторую пару точек $p$$p$  и $q$$q$ .

Этот перпендикуляр разбивает плоскость на две полуплоскости $H_{pq}$$H_{{pq}}$  и $H_{qp}$$H_{{qp}}$ , причём область Вороного точки p целиком содержится в одной из них, а область точки $q$$q$  — в другой. Область Вороного $V_p$$V_{p}$  точки $p$$p$  совпадает с пересечением всех таких полуплоскостей $H_{pq}$$H_{{pq}}$ :

$V_p=\underset{q\in <!--\; \in \; -->S/\{p\}}{\bigcap <!--\; \bigcap \; -->}{H}_{pq}$$V_{p}=\bigcap \limits _{q\in S/\{p\}}H_{pq}$ .

Таким образом, решение задачи сводится к вычислению такого пересечения для каждой точки $p$$p$ . Алгоритм может быть реализован с вычислительной сложностью $O(n^4)$$O(n^{4})$ .

Алгоритм ФорчунаПравить

Основная статья: Алгоритм Форчуна

 

Построение диаграммы алгоритмом Форчуна.

Алгоритм основан на применении заметающей прямой. Заметающая прямая — это вспомогательный объект, представляющий собой вертикальную прямую линию. На каждом шаге алгоритма диаграмма Вороного построена для множества, состоящего из заметающей прямой и точек слева от неё. При этом граница между областью Вороного, прямой и областями точек состоит из отрезков парабол (так как геометрическое место точек, равноудалённых от заданной точки и прямой — это парабола). Прямая движется слева направо. Каждый раз, когда она проходит через очередную точку, эта точка добавляется к уже построенному участку диаграммы. Добавление точки к диаграмме при использовании двоичного дерева поиска имеет сложность $O(\log <!--\; \; -->n)$$O(\log n)$ , всего точек $n$$n$ , а сортировка точек по $x$$x$ -координате может быть выполнена за $O(n\log <!--\; \; -->n)$$O(n\log n)$ , поэтому вычислительная сложность алгоритма Форчуна равна $O(n\log <!--\; \; -->n)$$O(n\log n)$ .

Рекурсивный алгоритмПравить

Основная идея рекурсивного алгоритма заключается в использовании метода динамического программирования. Исходное множество точек $S$$S$  разбивается на два подмножества $S_1$$S_{1}$  и $S_2$$S_{2}$ , для каждого из них строится диаграмма Вороного, а затем полученные диаграммы объединяются в одну. Разбиение множества $S$$S$  осуществляется при помощи прямой, разделяющей плоскость на две полуплоскости, так, чтобы в обеих полуплоскостях находилось примерно одинаковое количество точек. Объединение диаграмм Вороного множеств $S_1$$S_{1}$  и $S_2$$S_{2}$  может быть выполнено за время $O(n)$$O(n)$ , поэтому вычислительная сложность алгоритма равна $O(n\log <!--\; \; -->n)$$O(n\log n)$ .

ОбобщенияПравить

Диаграмму Вороного очевидным образом можно определить для множества точек в произвольном евклидовом пространстве, необязательно двумерном. Имеет место следующее утверждение: в $k$$k$ -мерном пространстве количество симплексов $k$$k$ -мерной триангуляции Делоне множества из $n$$n$  точек может достигать $O(n^{\lceil <!--\; \lceil \; -->\frac{k}{2}\rceil <!--\; \rceil \; -->})$$O(n^{{\lceil {\frac k2}\rceil }})$ . Следовательно, такой же порядок имеют расходы памяти, требуемой для хранения двойственной диаграммы Вороного.

Диаграмма Вороного может быть определена для пространства с метрикой, отличной от евклидовой. Однако в этом случае, границы между соседними областями Вороного могут не быть многообразиями первого порядка (например, при использовании манхэттенского расстояния).

Множество S может состоять не только из точек, но и из любых объектов, для которых определено расстояние до произвольной точки плоскости. В этом случае элементы множества S называют сайтами. В качестве примера можно привести диаграмму Вороного многоугольника, где сайты — это вершины и рёбра многоугольника. Такие диаграммы используются для построения срединных осей и широко применяются в задачах анализа изображений. Граница областей диаграммы Вороного многоугольника представляет собой объединение отрезков прямых и парабол.

ПрименениеПравить

Разбиение Вороного применяется в вычислительном материаловедении для создания синтетических поликристаллических агрегатов. Также используется в компьютерной графике для случайного разбиения поверхностей.

Метод Гольда (или «метод похищения площади») — метод интерполяции функции в 2D, применяемый, например, в геодезии. Строится диаграмма Вороного всех точек, после этого к ней добавляется искомая точка. Новая ячейка «отбирает» площадь у имеющихся; чем больше площади позаимствовано у (x_i, y_i, z_i), тем больше коэффициент при этой точке.

Также разбиение Вороного применяется при нахождении верхней оценки хроматического числа для евклидова пространства (проблема Нелсона-Эрдёша-Хадвигера) размерности 2 или 3. Здесь рассматривают разбиение плоскости на многоугольники Вороного для заданной решётки. Наилучшая оценка была найдена, как для 2-мерного, так и для 3-мерного пространств, при рассмотрении симметричного разбиения. Например, замощение плоскости шестиугольниками (в данном случае шестиугольник — многоугольник Вороного).

См. такжеПравить

• Задача поиска ближайшего соседа
• Ячейка Вигнера — Зейтца

СсылкиПравить

• Алгоритм Форчуна Архивная копия от 13 июня 2008 на Wayback Machine (англ.)
• Визуализатор алгоритма Форчуна