Interested Article - Диаграмма Вороного

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

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

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

История

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

Свойства

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

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

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

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

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

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

.

Таким образом, решение задачи сводится к вычислению такого пересечения для каждой точки . Алгоритм может быть реализован с вычислительной сложностью .

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

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

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

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

Основная идея рекурсивного алгоритма заключается в использовании метода динамического программирования . Исходное множество точек разбивается на два подмножества и , для каждого из них строится диаграмма Вороного, а затем полученные диаграммы объединяются в одну. Разбиение множества осуществляется при помощи прямой, разделяющей плоскость на две полуплоскости, так, чтобы в обеих полуплоскостях находилось примерно одинаковое количество точек. Объединение диаграмм Вороного множеств и может быть выполнено за время , поэтому вычислительная сложность алгоритма равна .

Обобщения

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

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

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

Применение

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

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

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

См. также

Ссылки

Источники

  1. от 23 апреля 2011 на Wayback Machine — М.: Мир, 1989. Стр. 295
  2. G.F. Voronoi. (фр.) // Journal für die reine und angewandte Mathematik. — 1908. — Vol. 134 . — P. 198—287 . 27 марта 2022 года.
  3. . MAXimal (26 января 2009). Дата обращения: 8 июня 2021. 8 июня 2021 года.
Источник —

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