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

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

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

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

История

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

Свойства

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

Алгоритмы построения

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

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

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

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

$V_{p}=\bigcap \limits _{q\in S/\{p\}}H_{pq}$.

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

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

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

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

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

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

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

Диаграмма Вороного с периодическими граничными условиями

Анимация, показывающая диаграмму Вороного с периодическими граничными условиями

Периодические граничные условия используются для моделирования бесконечной системы путем периодического повторения конечной системы во всех направлениях. Такой подход позволяет устранить граничные эффекты, не требуя при этом практически большого объема вычислений. Чтобы построить диаграмму Вороного с периодическими граничными условиями в дискретной среде с размерами MxN элементов, достаточно вычислить координаты соседних элементов по модулю M и N соответственно. Таким образом, элементы на правой границе дискретной сетки оказываются смежными с элементами на левой границе, а элементы на нижней границе оказываются смежными с элементами на верхней границе. Пример диаграммы Вороного с периодическими граничными условиями показан на изображение справа. Анимация демонстрирует периодичность диаграммы, прокручивая изображение по горизонтали и вертикали.

Обобщения

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

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

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

Применение

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

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

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

См. также

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

Ссылки

• Алгоритм Форчуна Архивная копия от 13 июня 2008 на Wayback Machine (англ.)
• Визуализатор алгоритма Форчуна
• Демонстрационная программа для алгоритма SFTessellation, которая создает диаграмму Вороного с использованием модели степного пожара