Русская Википедия:Диаграмма Вороного
Диаграмма Вороного конечного множества точек S на плоскости представляет такое разбиение плоскости, при котором каждая область этого разбиения образует множество точек, более близких к одному из элементов множества S, чем к любому другому элементу множества[1].
Названа в честь Георгия Феодосьевича Вороного, который изучил общий n-мерный случай в 1908 году[2]. Также известна как: мозаика Вороного, разбиение Вороного, разбиение Дирихле.
История
Впервые применение подобных конструкций приписывают Декарту в 1644 году. Дирихле использовал двумерные и трехмерные диаграммы Вороного в своём труде о квадратичных формах в 1850.
Свойства
Имеет тесную связь и взаимно-однозначное соответствие с триангуляцией Делоне. А именно, если соединить рёбрами точки, области Вороного которых граничат друг с другом, полученный граф будет являться триангуляцией Делоне.
Алгоритмы построения
Простой алгоритм
Рассмотрим серединный перпендикуляр отрезка, соединяющего некоторую пару точек <math>p</math> и <math>q</math>.
Этот перпендикуляр разбивает плоскость на две полуплоскости <math>H_{pq}</math> и <math>H_{qp}</math>, причём область Вороного точки p целиком содержится в одной из них, а область точки <math>q</math> — в другой. Область Вороного <math>V_p</math> точки <math>p</math> совпадает с пересечением всех таких полуплоскостей <math>H_{pq}</math>:
<math>V_p = \bigcap \limits_{q \in S / \{p\}} H_{pq}</math>.
Таким образом, решение задачи сводится к вычислению такого пересечения для каждой точки <math>p</math>. Алгоритм может быть реализован с вычислительной сложностью <math>O(n^4)</math>[3].
Алгоритм Форчуна
Алгоритм основан на применении заметающей прямой. Заметающая прямая — это вспомогательный объект, представляющий собой вертикальную прямую линию. На каждом шаге алгоритма диаграмма Вороного построена для множества, состоящего из заметающей прямой и точек слева от неё. При этом граница между областью Вороного, прямой и областями точек состоит из отрезков парабол (так как геометрическое место точек, равноудалённых от заданной точки и прямой — это парабола). Прямая движется слева направо. Каждый раз, когда она проходит через очередную точку, эта точка добавляется к уже построенному участку диаграммы. Добавление точки к диаграмме при использовании двоичного дерева поиска имеет сложность <math>O(\log n)</math>, всего точек <math>n</math>, а сортировка точек по <math>x</math>-координате может быть выполнена за <math>O(n \log n)</math>, поэтому вычислительная сложность алгоритма Форчуна равна <math>O(n \log n)</math>.
Рекурсивный алгоритм
Основная идея рекурсивного алгоритма заключается в использовании метода динамического программирования. Исходное множество точек <math>S</math> разбивается на два подмножества <math>S_1</math> и <math>S_2</math>, для каждого из них строится диаграмма Вороного, а затем полученные диаграммы объединяются в одну. Разбиение множества <math>S</math> осуществляется при помощи прямой, разделяющей плоскость на две полуплоскости, так, чтобы в обеих полуплоскостях находилось примерно одинаковое количество точек. Объединение диаграмм Вороного множеств <math>S_1</math> и <math>S_2</math> может быть выполнено за время <math>O(n)</math>, поэтому вычислительная сложность алгоритма равна <math>O(n \log n)</math>.
Обобщения
Диаграмму Вороного очевидным образом можно определить для множества точек в произвольном евклидовом пространстве, необязательно двумерном. Имеет место следующее утверждение: в <math>k</math>-мерном пространстве количество симплексов <math>k</math>-мерной триангуляции Делоне множества из <math>n</math> точек может достигать <math>O(n^{\lceil \frac k 2 \rceil})</math>. Следовательно, такой же порядок имеют расходы памяти, требуемой для хранения двойственной диаграммы Вороного.
Диаграмма Вороного может быть определена для пространства с метрикой, отличной от евклидовой. Однако в этом случае, границы между соседними областями Вороного могут не быть многообразиями первого порядка (например, при использовании манхэттенского расстояния).
Множество S может состоять не только из точек, но и из любых объектов, для которых определено расстояние до произвольной точки плоскости. В этом случае элементы множества S называют сайтами. В качестве примера можно привести диаграмму Вороного многоугольника, где сайты — это вершины и рёбра многоугольника. Такие диаграммы используются для построения срединных осей и широко применяются в задачах анализа изображений. Граница областей диаграммы Вороного многоугольника представляет собой объединение отрезков прямых и парабол.
Применение
Разбиение Вороного применяется в вычислительном материаловедении для создания синтетических поликристаллических агрегатов. Также используется в компьютерной графике для случайного разбиения поверхностей.
Метод Гольда (или «метод похищения площади») — метод интерполяции функции в 2D, применяемый, например, в геодезии. Строится диаграмма Вороного всех точек, после этого к ней добавляется искомая точка. Новая ячейка «отбирает» площадь у имеющихся; чем больше площади позаимствовано у (xi, yi, zi), тем больше коэффициент при этой точке.
Также разбиение Вороного применяется при нахождении верхней оценки хроматического числа для евклидова пространства (проблема Нелсона-Эрдёша-Хадвигера) размерности 2 или 3. Здесь рассматривают разбиение плоскости на многоугольники Вороного для заданной решётки. Наилучшая оценка была найдена, как для 2-мерного, так и для 3-мерного пространств, при рассмотрении симметричного разбиения. Например, замощение плоскости шестиугольниками (в данном случае шестиугольник — многоугольник Вороного).
См. также
Ссылки
Источники
Шаблон:Примечания Шаблон:Геометрические мозаики
- ↑ Ф. Препарата, М. Шеймос. Вычислительная геометрия: Введение. Шаблон:Wayback — М.: Мир, 1989. Стр. 295
- ↑ Шаблон:Статья
- ↑ Шаблон:Cite web
