- Диаграмма Вороного
-
Диаграмма Вороного конечного множества точек S на плоскости представляет такое разбиение плоскости, при котором каждая область этого разбиения образует множество точек, более близких к одному из элементов множества S, чем к любому другому элементу множества[1].
Названа в честь российского учёного Георгия Феодосьевича Вороного (1868—1908). Также известна как: мозаика Вороного, разбиение Вороного, разбиение Дирихле.
Содержание
История
Впервые применение подобных конструкций приписывают Декарту в 1644 году. Дирихле использовал двумерные и трехмерные диаграммы Вороного в своём труде о квадратичных формах в 1850.
Свойства
Имеет тесную связь и взаимооднозначное соответствие с триангуляцией Делоне. А именно, если соединить рёбрами точки, области Вороного которых граничат друг с другом, полученный граф будет являться триангуляцией Делоне.
Алгоритмы построения
Построение диаграммы алгоритмом Форчуна.Простой алгоритм
Рассмотрим серединный перпендикуляр отрезка, соединяющего некоторую пару точек
и
. Этот перпендикуляр разбивает плоскость на две полуплоскости
и
, причём область Вороного точки p целиком содержится в одной из них, а область точки
— в другой. Область Вороного
точки
совпадает с пересечением всех таких полуплоскостей
:
.
Таким образом, решение задачи сводится к вычислению такого пересечения для каждой точки
. Алгоритм может быть реализован с вычислительной сложностью
.
Алгоритм Форчуна
Алгоритм основан на применении заметающей прямой. Заметающая прямая — это вспомогательный объект, представляющий собой вертикальную прямую линию. На каждом шаге алгоритма диаграмма Вороного построена для множества, состоящего из заметающей прямой и точек слева от неё. При этом граница между областью Вороного прямой и областями точек состоит из отрезков парабол (так как геометрическое место точек, равноудалённых от заданной точки и прямой — это парабола). Прямая движется слева направо. Каждый раз, когда она проходит через очередную точку, эта точка добавляется к уже построенному участку диаграммы. Добавление точки к диаграмме при использовании двоичного дерева поиска имеет сложность
, всего точек
, а сортировка точек по
-координате может быть выполнена за
, поэтому вычислительная сложность алгоритма Форчуна равна
.
Рекурсивный алгоритм
Основная идея рекурсивного алгоритма заключается в использовании метода динамического программирования. Исходное множество точек
разбивается на два подмножества
и
, для каждого из них строится диаграмма Вороного, а затем полученные диаграммы объединяются в одну. Разбиение множества
осуществляется при помощи прямой, разделяющей плоскость на две полуплоскости, так, чтобы в обеих полуплоскостях находилось примерно одинаковое количество точек. Объединение диаграмм Вороного множеств
и
может быть выполнено за время
, поэтому вычислительная сложность алгоритма равна
.
Обобщения
Диаграмму Вороного очевидным образом можно определить для множества точек в произвольном евклидовом пространстве, необязательно двумерном. Имеет место следующее утверждение: в
-мерном пространстве количество симплексов
-мерной триангуляции Делоне множества из
точек может достигать
. Следовательно, такой же порядок имеют расходы памяти, требуемой для хранения двойственной диаграммы Вороного.
Диаграмма Вороного может быть определена для пространства с метрикой, отличной от евклидовой. Однако в этом случае границы между соседними областями Вороного могут не быть многообразиями первого порядка (например, при использовании манхэттенского расстояния).
Множество S может состоять не только из точек, но и из любых объектов, для которых определено расстояние до произвольной точки плоскости. В этом случае элементы множества S называют сайтами. В качестве примера можно привести диаграмму Вороного многоугольника, где в роли сайтов выступают вершины и рёбра многоугольника. Такие диаграммы используются для построения срединных осей и широко применяются в задачах анализа изображений. Граница областей диаграммы Вороного многоугольника представляет собой объединение отрезков прямых и парабол.
Применение
Разбиение Вороного применяется в вычислительном материаловедении для создания синтетических поликристаллических агрегатов. Также используется в компьютерной графике для случайного разбиения поверхностей.
Метод Гольда (или «метод похищения площади») — метод интерполяции функции в 2D, применяемый, например, в геодезии. Строится диаграмма Вороного всех точек, после этого к ней добавляется искомая точка. Новая ячейка «отбирает» площадь у имеющихся; чем больше площади позаимствовано у (xi, yi, zi), тем больше коэффициент при этой точке.
См. также
- Задача поиска ближайшего соседа
- Ячейка Вигнера — Зейтца
Ссылки
Источники
- ↑ Ф. Препарата, М. Шеймос. Вычислительная геометрия: Введение. — М.: Мир, 1989. Стр. 295
Категории:- Вычислительная геометрия
- Геометрические алгоритмы
- Комбинаторная геометрия
Wikimedia Foundation. 2010.