Диаграмма Вороного
Диаграмма Вороного конечного множества точек S на плоскости представляет такое разбиение плоскости, при котором каждая область этого разбиения образует множество точек, более близких к одному из элементов множества S, чем к любому другому элементу множества[1].
Названа в честь Георгия Феодосьевича Вороного, который изучил общий n-мерный случай в 1908 году[2]. Также известна как: мозаика Вороного, разбиение Вороного, разбиение Дирихле.
История
Впервые применение подобных конструкций приписывают Декарту в 1644 году. Дирихле использовал двумерные и трехмерные диаграммы Вороного в своём труде о квадратичных формах в 1850.
Свойства
Имеет тесную связь и взаимно-однозначное соответствие с триангуляцией Делоне. А именно, если соединить рёбрами точки, области Вороного которых граничат друг с другом, полученный граф будет являться триангуляцией Делоне.
Алгоритмы построения
Простой алгоритм
Рассмотрим серединный перпендикуляр отрезка, соединяющего некоторую пару точек [math]\displaystyle{ p }[/math] и [math]\displaystyle{ q }[/math].
Этот перпендикуляр разбивает плоскость на две полуплоскости [math]\displaystyle{ H_{pq} }[/math] и [math]\displaystyle{ H_{qp} }[/math], причём область Вороного точки p целиком содержится в одной из них, а область точки [math]\displaystyle{ q }[/math] — в другой. Область Вороного [math]\displaystyle{ V_p }[/math] точки [math]\displaystyle{ p }[/math] совпадает с пересечением всех таких полуплоскостей [math]\displaystyle{ H_{pq} }[/math]:
[math]\displaystyle{ V_p = \bigcap \limits_{q \in S / \{p\}} H_{pq} }[/math].
Таким образом, решение задачи сводится к вычислению такого пересечения для каждой точки [math]\displaystyle{ p }[/math]. Алгоритм может быть реализован с вычислительной сложностью [math]\displaystyle{ O(n^4) }[/math][3].
Алгоритм Форчуна
Алгоритм основан на применении заметающей прямой. Заметающая прямая — это вспомогательный объект, представляющий собой вертикальную прямую линию. На каждом шаге алгоритма диаграмма Вороного построена для множества, состоящего из заметающей прямой и точек слева от неё. При этом граница между областью Вороного, прямой и областями точек состоит из отрезков парабол (так как геометрическое место точек, равноудалённых от заданной точки и прямой — это парабола). Прямая движется слева направо. Каждый раз, когда она проходит через очередную точку, эта точка добавляется к уже построенному участку диаграммы. Добавление точки к диаграмме при использовании двоичного дерева поиска имеет сложность [math]\displaystyle{ O(\log n) }[/math], всего точек [math]\displaystyle{ n }[/math], а сортировка точек по [math]\displaystyle{ x }[/math]-координате может быть выполнена за [math]\displaystyle{ O(n \log n) }[/math], поэтому вычислительная сложность алгоритма Форчуна равна [math]\displaystyle{ O(n \log n) }[/math].
Рекурсивный алгоритм
Основная идея рекурсивного алгоритма заключается в использовании метода динамического программирования. Исходное множество точек [math]\displaystyle{ S }[/math] разбивается на два подмножества [math]\displaystyle{ S_1 }[/math] и [math]\displaystyle{ S_2 }[/math], для каждого из них строится диаграмма Вороного, а затем полученные диаграммы объединяются в одну. Разбиение множества [math]\displaystyle{ S }[/math] осуществляется при помощи прямой, разделяющей плоскость на две полуплоскости, так, чтобы в обеих полуплоскостях находилось примерно одинаковое количество точек. Объединение диаграмм Вороного множеств [math]\displaystyle{ S_1 }[/math] и [math]\displaystyle{ S_2 }[/math] может быть выполнено за время [math]\displaystyle{ O(n) }[/math], поэтому вычислительная сложность алгоритма равна [math]\displaystyle{ O(n \log n) }[/math].
Обобщения
Диаграмму Вороного очевидным образом можно определить для множества точек в произвольном евклидовом пространстве, необязательно двумерном. Имеет место следующее утверждение: в [math]\displaystyle{ k }[/math]-мерном пространстве количество симплексов [math]\displaystyle{ k }[/math]-мерной триангуляции Делоне множества из [math]\displaystyle{ n }[/math] точек может достигать [math]\displaystyle{ O(n^{\lceil \frac k 2 \rceil}) }[/math]. Следовательно, такой же порядок имеют расходы памяти, требуемой для хранения двойственной диаграммы Вороного.
Диаграмма Вороного может быть определена для пространства с метрикой, отличной от евклидовой. Однако в этом случае, границы между соседними областями Вороного могут не быть многообразиями первого порядка (например, при использовании манхэттенского расстояния).
Множество S может состоять не только из точек, но и из любых объектов, для которых определено расстояние до произвольной точки плоскости. В этом случае элементы множества S называют сайтами. В качестве примера можно привести диаграмму Вороного многоугольника, где сайты — это вершины и рёбра многоугольника. Такие диаграммы используются для построения срединных осей и широко применяются в задачах анализа изображений. Граница областей диаграммы Вороного многоугольника представляет собой объединение отрезков прямых и парабол.
Применение
Разбиение Вороного применяется в вычислительном материаловедении для создания синтетических поликристаллических агрегатов. Также используется в компьютерной графике для случайного разбиения поверхностей.
Метод Гольда (или «метод похищения площади») — метод интерполяции функции в 2D, применяемый, например, в геодезии. Строится диаграмма Вороного всех точек, после этого к ней добавляется искомая точка. Новая ячейка «отбирает» площадь у имеющихся; чем больше площади позаимствовано у (xi, yi, zi), тем больше коэффициент при этой точке.
Также разбиение Вороного применяется при нахождении верхней оценки хроматического числа для евклидова пространства (проблема Нелсона-Эрдёша-Хадвигера) размерности 2 или 3. Здесь рассматривают разбиение плоскости на многоугольники Вороного для заданной решётки. Наилучшая оценка была найдена, как для 2-мерного, так и для 3-мерного пространств, при рассмотрении симметричного разбиения. Например, замощение плоскости шестиугольниками (в данном случае шестиугольник — многоугольник Вороного).
См. также
Ссылки
- Алгоритм Форчуна Архивная копия от 13 июня 2008 на Wayback Machine (англ.)
- Визуализатор алгоритма Форчуна
Источники
- ↑ Ф. Препарата, М. Шеймос. Вычислительная геометрия: Введение. Архивная копия от 23 апреля 2011 на Wayback Machine — М.: Мир, 1989. Стр. 295
- ↑ G.F. Voronoi. Nouvelles applications des paramètres continus à la théorie de formes quadratiques (фр.) // Journal für die reine und angewandte Mathematik. — 1908. — Vol. 134. — P. 198—287.
- ↑ Диаграмма Вороного. MAXimal (26 января 2009). Дата обращения: 8 июня 2021. Архивировано 8 июня 2021 года.
