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

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

Диаграмма Вороного названа в честь математика Георгия Вороного , а также называется мозаикой Вороного , разложением Вороного , разбиением Вороного или мозаикой Дирихле (в честь Питера Густава Лежена Дирихле ). Ячейки Вороного также известны как многоугольники Тиссена , в честь Альфреда Х. Тиссена . ^{[1] [2] [3]} Диаграммы Вороного имеют практическое и теоретическое применение во многих областях, в основном в науке и технике , но также и в изобразительном искусстве . ^{[4] [5]}

В простейшем случае, показанном на первом рисунке, нам дан конечный набор точек на евклидовой плоскости . В этом случае каждый узел является одной из этих заданных точек, а его соответствующая ячейка Вороного состоит из каждой точки на евклидовой плоскости, для которой является ближайшим узлом: расстояние до меньше или равно минимальному расстоянию до любого другого узла . Для одного другого узла точки, которые ближе к , чем к , или одинаково удалены, образуют замкнутое полупространство , граница которого является перпендикуляром к отрезку прямой . Ячейка является пересечением всех этих полупространств, и, следовательно, это выпуклый многоугольник . ^[6] Когда две ячейки на диаграмме Вороного имеют общую границу, это отрезок прямой , луч или линия , состоящие из всех точек на плоскости, которые равноудалены от двух их ближайших узлов. Вершины диаграммы, где встречаются три или более из этих границ, являются точками, которые имеют три или более одинаково удаленных ближайших узлов.${\displaystyle \{p_{1},\точки p_{n}\}}$${\displaystyle p_{k}}$${\displaystyle R_{k}}$${\displaystyle p_{k}}$${\displaystyle p_{k}}$${\displaystyle p_{j}}$${\displaystyle p_{j}}$${\displaystyle p_{k}}$${\displaystyle p_{j}}$${\displaystyle p_{j}p_{k}}$${\displaystyle R_{k}}$${\displaystyle n-1}$

Пусть будет метрическим пространством с функцией расстояния . Пусть будет набором индексов и пусть будет кортежем (индексированным набором) непустых подмножеств (сайтов) в пространстве . Ячейка Вороного, или область Вороного, , связанная с сайтом, — это множество всех точек, расстояние до которых не больше, чем расстояние до других сайтов , где — любой индекс, отличный от . Другими словами, если обозначает расстояние между точкой и подмножеством , то${\textstyle X}$${\textstyle д}$${\textstyle К}$${\textstyle (P_{k})_{k\in K}}$${\textstyle X}$${\textstyle Р_{к}}$${\textstyle П_{к}}$${\textstyle X}$${\textstyle П_{к}}$${\textstyle P_{j}}$${\textstyle j}$${\textstyle к}$${\textstyle d(x,\,A)=\inf\{d(x,\,a)\mid a\in A\}}$${\textstyle x}$${\textstyle А}$

$${\displaystyle R_{k}=\{x\in X\mid d(x,P_{k})\leq d(x,P_{j})\;{\text{для всех}}\;j\neq k\}}$$

Диаграмма Вороного — это просто кортеж ячеек . В принципе, некоторые из сайтов могут пересекаться и даже совпадать (ниже описано применение для сайтов, представляющих магазины), но обычно предполагается, что они не пересекаются. Кроме того, в определении допускается бесконечно много сайтов (эта настройка имеет приложения в геометрии чисел и кристаллографии ), но, опять же, во многих случаях рассматривается только конечное число сайтов.${\textstyle (R_{k})_{k\in K}}$

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

В обычном евклидовом пространстве мы можем переписать формальное определение в обычных терминах. Каждый многоугольник Вороного связан с точкой-генератором . Пусть будет множеством всех точек в евклидовом пространстве. Пусть будет точкой, которая порождает свою область Вороного , которая порождает , и которая порождает , и так далее. Тогда, как выразился Тран и др . ^[7], «все местоположения в многоугольнике Вороного находятся ближе к точке-генератору этого многоугольника, чем любая другая точка-генератор на диаграмме Вороного на евклидовой плоскости».${\textstyle Р_{к}}$${\textstyle П_{к}}$${\textstyle X}$${\textstyle P_{1}}$${\textstyle Р_{1}}$${\textstyle P_{2}}$${\textstyle Р_{2}}$${\textstyle P_{3}}$${\textstyle Р_{3}}$

В качестве простого примера рассмотрим группу магазинов в городе. Предположим, мы хотим оценить количество клиентов данного магазина. При прочих равных условиях (цена, продукты, качество обслуживания и т. д.) разумно предположить, что клиенты выбирают предпочтительный магазин просто по соображениям расстояния: они пойдут в магазин, расположенный ближе всего к ним. В этом случае ячейку Вороного данного магазина можно использовать для приблизительной оценки количества потенциальных клиентов, посещающих этот магазин (который моделируется точкой в ​​нашем городе).${\displaystyle R_{k}}$${\displaystyle P_{k}}$

Для большинства городов расстояние между точками можно измерить с помощью известного евклидова расстояния :

${\displaystyle \ell _{2}=d\left[\left(a_{1},a_{2}\right),\left(b_{1},b_{2}\right)\right]={\sqrt {\left(a_{1}-b_{1}\right)^{2}+\left(a_{2}-b_{2}\right)^{2}}}}$

или манхэттенское расстояние :

${\displaystyle d\left[\left(a_{1},a_{2}\right),\left(b_{1},b_{2}\right)\right]=\left|a_{1}-b_{1}\right|+\left|a_{2}-b_{2}\right|}$.

Соответствующие диаграммы Вороного выглядят по-разному для разных метрик расстояния.

• Двойственный граф для диаграммы Вороного (в случае евклидова пространства с точечными узлами) соответствует триангуляции Делоне для того же набора точек.
• Ближайшая пара точек соответствует двум соседним ячейкам на диаграмме Вороного.
• Предположим, что задана евклидова плоскость и дискретный набор точек. Тогда две точки набора являются смежными на выпуклой оболочке тогда и только тогда, когда их ячейки Вороного имеют общую бесконечно длинную сторону.
• Если пространство является нормированным пространством и расстояние до каждого узла достигается (например, когда узел является компактным множеством или замкнутым шаром), то каждая ячейка Вороного может быть представлена ​​как объединение отрезков прямых, исходящих из узлов. ^[8] Как показано там, это свойство не обязательно выполняется, когда расстояние не достигается.
• При относительно общих условиях (пространство является, возможно, бесконечномерным равномерно выпуклым пространством , может быть бесконечно много участков общей формы и т. д.) ячейки Вороного обладают определенным свойством устойчивости: небольшое изменение формы участков, например, изменение, вызванное некоторым переносом или искажением, приводит к небольшому изменению формы ячеек Вороного. Это геометрическая устойчивость диаграмм Вороного. ^[9] Как там показано, это свойство не выполняется в общем случае, даже если пространство двумерно (но неравномерно выпукло и, в частности, неевклидово), а участки являются точками.

Неформальное использование диаграмм Вороного можно проследить до Декарта в 1644 году. ^[10] Питер Густав Лежен Дирихле использовал двумерные и трехмерные диаграммы Вороного в своем исследовании квадратичных форм в 1850 году. Британский врач Джон Сноу использовал диаграмму, похожую на диаграмму Вороного, в 1854 году, чтобы проиллюстрировать, как большинство людей, умерших во время вспышки холеры на Брод-стрит, жили ближе к зараженному насосу на Брод-стрит, чем к любому другому водяному насосу.

Диаграммы Вороного названы в честь Георгия Феодосиевича Вороного , который определил и изучил общий n -мерный случай в 1908 году. ^[11] Диаграммы Вороного, которые используются в геофизике и метеорологии для анализа пространственно распределенных данных, называются полигонами Тиссена в честь американского метеоролога Альфреда Х. Тиссена , который использовал их для оценки количества осадков по разбросанным измерениям в 1911 году. Другие эквивалентные названия для этой концепции (или ее отдельных важных случаев): многогранники Вороного, многоугольники Вороного, область(и) влияния, разложение Вороного, мозаика(и) Вороного, мозаика(и) Дирихле.

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

• Двумерная решетка дает нерегулярную сотовую мозаику с равными шестиугольниками с точечной симметрией; в случае правильной треугольной решетки она является правильной; в случае прямоугольной решетки шестиугольники сводятся к прямоугольникам в строках и столбцах; квадратная решетка дает правильную мозаику квадратов; обратите внимание, что прямоугольники и квадраты также могут быть получены другими решетками (например, решетка, определяемая векторами (1,0) и (1/2,1/2), дает квадраты).
• Простая кубическая решетка дает кубические соты .
• Гексагональная плотноупакованная решетка дает мозаичное изображение пространства с трапециевидно-ромбическими додекаэдрами .
• Гранецентрированная кубическая решетка дает мозаичное изображение пространства с ромбическими додекаэдрами .
• Объемно -центрированная кубическая решетка дает мозаичное изображение пространства с усеченными октаэдрами .
• Параллельные плоскости с правильными треугольными решетками, выровненные по центрам друг друга, образуют шестиугольные призматические соты .
• Некоторые объемно-центрированные тетрагональные решетки создают мозаику пространства с ромбо-гексагональными додекаэдрами .

Некоторые объемно-центрированные тетрагональные решетки создают мозаику пространства с ромбо-гексагональными додекаэдрами .

Для набора точек ( x ,  y ), где x принадлежит дискретному множеству X , а y принадлежит дискретному множеству Y , мы получаем прямоугольные плитки с точками, не обязательно находящимися в их центрах.

Хотя обычная ячейка Вороного определяется как множество точек, ближайших к одной точке в S , ячейка Вороного n -го порядка определяется как множество точек, имеющих определенный набор из n точек в S в качестве своих n ближайших соседей. Диаграммы Вороного более высокого порядка также подразделяют пространство.

Диаграммы Вороного более высокого порядка могут быть сгенерированы рекурсивно. Чтобы сгенерировать диаграмму Вороного n- ^го порядка из множества  S , начните с диаграммы ( n  − 1) ^-го порядка и замените каждую ячейку, сгенерированную X  = { x ₁ ,  x ₂ , ...,  x _{n −1} }, диаграммой Вороного, сгенерированной на множестве  S  −  X .

Для набора из n точек диаграмма Вороного ( n  − 1) ^-го порядка называется диаграммой Вороного самой дальней точки.

Для заданного набора точек S  = { p ₁ ,  p ₂ , ...,  p _n } диаграмма Вороного для самой дальней точки делит плоскость на ячейки, в которых та же самая точка P является самой дальней точкой. Точка P имеет ячейку в диаграмме Вороного для самой дальней точки тогда и только тогда , когда она является вершиной выпуклой оболочки P . Пусть H  = { h ₁ ,  h ₂ , ...,  h _k } будет выпуклой оболочкой P ; то диаграмма Вороного для самой дальней точки представляет собой разбиение плоскости на k ячеек, по одной для каждой точки в H , со свойством, что точка q лежит в ячейке, соответствующей узлу h _i, тогда и только тогда, когда d( q , h _i ) > d( q , p _j ) для каждого p _j  ∈  S с h _i ≠ p _j , где d( p , q ) — евклидово расстояние между двумя точками p и  q . ^{[12] [13]}

Границы ячеек в диаграмме Вороного с самой дальней точкой имеют структуру топологического дерева , с бесконечными лучами в качестве его листьев. Каждое конечное дерево изоморфно дереву, образованному таким образом из диаграммы Вороного с самой дальней точкой. ^[14]

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

Взвешенная диаграмма Вороного — это диаграмма, в которой функция пары точек для определения ячейки Вороного является функцией расстояния, измененной мультипликативными или аддитивными весами, назначенными точкам генератора. В отличие от случая ячеек Вороного, определенных с использованием расстояния, которое является метрикой , в этом случае некоторые ячейки Вороного могут быть пустыми. Диаграмма мощности — это тип диаграммы Вороного, определяемой из набора кругов с использованием расстояния мощности ; ее также можно рассматривать как взвешенную диаграмму Вороного, в которой вес, определенный из радиуса каждого круга, добавляется к квадрату евклидова расстояния от центра круга. ^[15]

Диаграмма Вороного точек в -мерном пространстве может иметь вершины, требующие той же границы для объема памяти, необходимого для хранения ее явного описания. Поэтому диаграммы Вороного часто нецелесообразны для умеренных или высоких размерностей. Более эффективной с точки зрения пространства альтернативой является использование приближенных диаграмм Вороного . ^[16]${\displaystyle n}$${\displaystyle д}$${\textstyle O(n^{\lceil d/2\rceil})}$

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

Он используется в метеорологии и инженерной гидрологии для нахождения весов для данных об осадках станций на площади (водосборе). Точки, образующие полигоны, являются различными станциями, которые регистрируют данные об осадках. Перпендикуляры проводятся к линии, соединяющей любые две станции. Это приводит к образованию полигонов вокруг станций. Площадь, касающаяся точки станции, известна как область влияния станции. Среднее количество осадков рассчитывается по формуле${\displaystyle (A_{i})}$${\displaystyle {\bar {P}}={\frac {\sum A_{i}P_{i}}{\sum A_{i}}}}$

• В классической археологии , в частности в истории искусств , симметрия голов статуй анализируется для определения типа статуи, которой могла принадлежать отрубленная голова. Примером этого, в котором использовались ячейки Вороного, была идентификация головы Сабуроффа , которая использовала полигональную сетку высокого разрешения . ^{[17] [18]}
• В диалектометрии ячейки Вороного используются для обозначения предполагаемой языковой преемственности между точками исследования.
• В политической науке диаграммы Вороного использовались для изучения многомерной многопартийной конкуренции. ^[19]

• В биологии диаграммы Вороного используются для моделирования ряда различных биологических структур, включая клетки ^[20] и микроархитектуру костей. ^[21] Действительно, мозаики Вороного работают как геометрический инструмент для понимания физических ограничений, которые управляют организацией биологических тканей. ^[22]
• В гидрологии диаграммы Вороного используются для расчета количества осадков на определенной территории на основе серии точечных измерений. В этом случае их обычно называют полигонами Тиссена.
• В экологии диаграммы Вороного используются для изучения закономерностей роста лесов и лесных пологов, а также могут быть полезны при разработке прогностических моделей лесных пожаров.
• В этологии диаграммы Вороного используются для моделирования областей опасности в теории эгоистичного стада .
• В вычислительной химии лиганд-связывающие сайты преобразуются в диаграммы Вороного для приложений машинного обучения (например, для классификации связывающих карманов в белках). ^[23] В других приложениях ячейки Вороного, определяемые положениями ядер в молекуле, используются для вычисления атомных зарядов . Это делается с помощью метода плотности деформации Вороного .
• В астрофизике диаграммы Вороного используются для генерации адаптивных зон сглаживания на изображениях, добавляя потоки сигнала на каждой из них. Основная цель этих процедур — поддерживать относительно постоянное отношение сигнал/шум на всех изображениях.
• В вычислительной гидродинамике мозаика Вороного набора точек может использоваться для определения вычислительных областей, используемых в методах конечных объемов , например, в космологическом коде с подвижной сеткой AREPO. ^[24]
• В вычислительной физике диаграммы Вороного используются для расчета профилей объекта с помощью теневой съемки и протонной радиографии в физике высокой плотности энергии . ^[25]

• В медицинской диагностике модели мышечной ткани, основанные на диаграммах Вороного, могут использоваться для выявления нервно-мышечных заболеваний. ^[22]
• В эпидемиологии диаграммы Вороного могут использоваться для сопоставления источников инфекций при эпидемиях. Одно из первых применений диаграмм Вороного было реализовано Джоном Сноу для изучения вспышки холеры на Брод-стрит в Сохо, Англия, в 1854 году. Он показал корреляцию между жилыми районами на карте Центрального Лондона, жители которых использовали определенный водяной насос, и районами с наибольшим количеством смертей из-за вспышки. ^[26]

• В физике полимеров диаграммы Вороного можно использовать для представления свободных объемов полимеров.
• В материаловедении поликристаллические микроструктуры в металлических сплавах обычно представляют с помощью мозаик Вороного.
• При росте островов диаграмма Вороного используется для оценки скорости роста отдельных островов. ^{[27] [28] [29] [30] [31]}
• В физике твердого тела ячейка Вигнера -Зейтца представляет собой мозаику Вороного твердого тела, а зона Бриллюэна представляет собой мозаику Вороного обратного ( волнового ) пространства кристаллов, имеющих симметрию пространственной группы.
• В авиации диаграммы Вороного накладываются на океанические карты для определения ближайшего аэродрома для изменения маршрута полета (см. ETOPS ) по мере выполнения самолетом своего плана полета.
• В архитектуре узоры Вороного легли в основу победившего проекта реконструкции Центра искусств Голд-Кост . ^[32]
• В городском планировании диаграммы Вороного могут использоваться для оценки системы зон погрузки грузов. ^[33]
• В горнодобывающей промышленности полигоны Вороного используются для оценки запасов ценных материалов, минералов или других ресурсов. В качестве набора точек в полигонах Вороного используются разведочные скважины.
• В поверхностной метрологии тесселяция Вороного может использоваться для моделирования шероховатости поверхности . ^[34]
• В робототехнике некоторые стратегии управления и алгоритмы планирования пути ^[35] многороботных систем основаны на разбиении среды по Вороному. ^{[36] [37]}

• Структура данных местоположения точки может быть построена поверх диаграммы Вороного для ответа на запросы ближайшего соседа , где требуется найти объект, который находится ближе всего к заданной точке запроса. Запросы ближайшего соседа имеют многочисленные приложения. Например, может потребоваться найти ближайшую больницу или наиболее похожий объект в базе данных . Большое приложение — это векторное квантование , обычно используемое при сжатии данных .
• В геометрии диаграммы Вороного можно использовать для нахождения наибольшего пустого круга среди множества точек и в охватывающем его многоугольнике; например, для строительства нового супермаркета как можно дальше от всех существующих, расположенных в определенном городе.
• Диаграммы Вороного вместе с диаграммами Вороного для самой дальней точки используются для эффективных алгоритмов вычисления округлости набора точек. ^[12] Подход Вороного также применяется для оценки округлости/ круглости при оценке набора данных с помощью координатно-измерительной машины .
• Нули итерированных производных рациональной функции на комплексной плоскости накапливаются на ребрах диаграммы Вороного множества полюсов (теорема Пойа-Шайреса ^[38] ).

• В сетевых технологиях диаграммы Вороного можно использовать для оценки пропускной способности беспроводной сети .
• В компьютерной графике диаграммы Вороного используются для расчета 3D-геометрических моделей дробления/трещин. Они также используются для процедурной генерации органических или лавоподобных текстур.
• В автономной навигации робота диаграммы Вороного используются для поиска четких маршрутов. Если точки являются препятствиями, то края графа будут маршрутами, наиболее удаленными от препятствий (и теоретически от любых столкновений).
• В машинном обучении диаграммы Вороного используются для проведения 1-NN -классификаций. ^[39]
• При реконструкции глобальной сцены, в том числе с использованием случайных датчиков и нестационарного потока в кильватерном следе, геофизических данных и данных трехмерной турбулентности, мозаики Вороного используются с глубоким обучением . ^[40]
• При разработке пользовательского интерфейса шаблоны Вороного можно использовать для вычисления наилучшего состояния наведения для заданной точки. ^[41]

Известно несколько эффективных алгоритмов для построения диаграмм Вороного, как напрямую (как сама диаграмма), так и косвенно, начиная с триангуляции Делоне и затем получая ее двойственную. Прямые алгоритмы включают алгоритм Форчуна , алгоритм O ( n log( n )) для генерации диаграммы Вороного из набора точек на плоскости. Алгоритм Боуера–Уотсона , алгоритм O ( n log( n )) до O ( n ² ) для генерации триангуляции Делоне в любом количестве измерений, может быть использован в косвенном алгоритме для диаграммы Вороного. Алгоритм Jump Flooding может генерировать приблизительные диаграммы Вороного за постоянное время и подходит для использования на обычном графическом оборудовании. ^{[42] [43]}

Алгоритм Ллойда и его обобщение с помощью алгоритма Линде–Бузо–Грея (также известного как кластеризация k-средних ) используют построение диаграмм Вороного в качестве подпрограммы. Эти методы чередуют шаги, на которых строится диаграмма Вороного для набора исходных точек, и шаги, на которых исходные точки перемещаются в новые местоположения, которые находятся ближе к центру в пределах их ячеек. Эти методы могут использоваться в пространствах произвольной размерности для итеративной сходимости к специализированной форме диаграммы Вороного, называемой центроидальной тесселяцией Вороного , где узлы перемещаются в точки, которые также являются геометрическими центрами их ячеек.

Сетки Вороного также можно создавать в 3D.

• 
  Случайные точки в 3D для формирования 3D разбиения Вороного
• 
  3D сетка Вороного из 25 случайных точек
• 
  3D сетка Вороного из 25 случайных точек с непрозрачностью 0,3 и точками
• 
  3D сетка Вороного из 25 случайных точек выпуклых многогранников

На Викискладе есть медиафайлы по теме « Диаграммы Вороного» .

• Вайсштейн, Эрик В. «Диаграмма Вороного». Математический мир .
• Диаграммы Вороного в CGAL , библиотеке алгоритмов вычислительной геометрии
• Демонстрационная программа для алгоритма SFTessellation, которая создает диаграмму Вороного с использованием модели степного пожара