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

Тип плоской перегородки

20 точек и их ячейки Вороного (увеличенная версия ниже)

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

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

Самый простой случай

В простейшем случае, показанном на первой картинке, нам дан конечный набор точек евклидовой плоскости . В этом случае каждый сайт является одной из этих заданных точек, а соответствующая ему ячейка Вороного состоит из каждой точки евклидовой плоскости, для которой является ближайшим узлом: расстояние до которого меньше или равно минимальному расстоянию до любого другого узла . Для другого узла точки, которые находятся ближе к , чем к или одинаково удалены, образуют замкнутое полупространство , граница которого является серединным перпендикуляром отрезка прямой . Ячейка является пересечением всех этих полупространств и, следовательно, является выпуклым многоугольником . ^[6] Когда две ячейки на диаграмме Вороного имеют общую границу, это отрезок , луч или линия, состоящая из всех точек плоскости, которые равноудалены от двух ближайших к ним точек. Вершины диаграммы , где встречаются три или более из этих границ, представляют собой точки, имеющие три или более одинаково удаленных ближайших узла. ${\displaystyle \{p_{1},\dots 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 d}$ ${\textstyle K}$ ${\textstyle (P_{k})_{k\in K}}$ ${\textstyle X}$ ${\textstyle R_{k}}$ ${\textstyle P_{k}}$ ${\textstyle X}$ ${\textstyle P_{k}}$ ${\textstyle P_{j}}$ ${\textstyle j}$ ${\textstyle k}$ ${\textstyle d(x,\,A)=\inf\{d(x,\,a)\mid a\in A\}}$ ${\textstyle x}$ ${\textstyle A}$

$${\displaystyle R_{k}=\{x\in X\mid d(x,P_{k})\leq d(x,P_{j})\;{\text{for all}}\;j\neq k\}}$$

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

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

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

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

Диаграммы Вороного по 20 точкам по двум разным метрикам

Характеристики

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

История и исследования

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

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

Примеры

Это фрагмент диаграммы Вороного случайного набора точек в трехмерном блоке. В общем, поперечное сечение трехмерной мозаики Вороного само по себе не является двумерной мозаикой Вороного.

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

• 2D-решетка представляет собой неправильную сотовую мозаику с одинаковыми шестиугольниками с точечной симметрией; в случае правильной треугольной решетки она правильна; в случае прямоугольной решетки шестиугольники сводятся к прямоугольникам в строках и столбцах; квадратная решетка дает правильную мозаику квадратов ; обратите внимание, что прямоугольники и квадраты также могут быть созданы другими решетками (например, решетка, определяемая векторами (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 d}$ ${\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]
• В вычислительной физике диаграммы Вороного используются для расчета профилей объекта с помощью Shadowgraph и протонной радиографии в физике высокой плотности энергии . ^[25]

Здоровье

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

Инженерное дело

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

Геометрия

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

Информатика

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

Гражданское право и планирование

• В Мельбурне учащиеся государственных школ всегда имеют право посещать ближайшую к месту их проживания начальную или среднюю школу, если измерять расстояние по прямой. Таким образом, карта школьных зон представляет собой диаграмму Вороного. ^[41]

Пекарня

• Украинский кондитер Динара Касько использует математические принципы диаграммы Вороного для создания силиконовых форм, изготовленных на 3D-принтере, для придания формы своим оригинальным тортам. ^[42]

Алгоритмы

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

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

Вороной в 3D

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

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

Смотрите также

• Триангуляция Делоне
• Сегментация карты
• Метод природных элементов
• Интерполяция естественных соседей
• Интерполяция ближайшего соседа
• Схема мощности
• Вороной полюс

Примечания

1. Берроу, Питер А.; Макдоннелл, Рэйчел; Макдоннелл, Рэйчел А.; Ллойд, Кристофер Д. (2015). «8.11 Ближайшие соседи: многоугольники Тиссена (Дирихле / Ворони)». Принципы географических информационных систем . Издательство Оксфордского университета. стр. 160–. ISBN 978-0-19-874284-5.
2. Лонгли, Пол А.; Гудчайлд, Майкл Ф.; Магуайр, Дэвид Дж.; Ринд, Дэвид В. (2005). «14.4.4.1 Многоугольники Тиссена». Географические информационные системы и наука . Уайли. стр. 333–. ISBN 978-0-470-87001-3.
3. Сен, Зекай (2016). «2.8.1 Полигоны Делани, Варони и Тиссена». Принципы пространственного моделирования в науках о Земле . Спрингер. стр. 57–. ISBN 978-3-319-41758-5.
4. Ауренхаммер, Франц (1991). «Диаграммы Вороного - обзор фундаментальной геометрической структуры данных». Обзоры вычислительной техники ACM . 23 (3): 345–405. дои : 10.1145/116873.116880. S2CID  4613674.
5. Окабе, Ацуюки; Бутс, Барри; Сугихара, Кокичи; Чиу, Сунг Нок (2000). Пространственные замощения - концепции и применение диаграмм Вороного (2-е изд.). Джон Уайли. ISBN 978-0-471-98635-5.
6. Бойд, Стивен; Ванденберге, Ливен (2004). Выпуклая оптимизация . Упражнение 2.9: Издательство Кембриджского университета. п. 60.{{cite book}}: CS1 maint: местоположение ( ссылка )
7. Тран, QT; Тайнар, Д.; Сафар, М. (2009). Транзакции в крупномасштабных системах, ориентированных на данные и знания . п. 357. ИСБН 9783642037214.
8. Рим 2009.
9. Рим 2011.
10. Сенешаль, Марджори (21 мая 1993 г.). «Математические структуры: пространственная мозаика. Концепции и приложения диаграмм Вороного. Ацуюки Окабе, Барри Бутс и Кокичи Сугихара. Уайли, Нью-Йорк, 1992. xii, 532 стр., иллюстр. $ 89,95. Серия Уайли по вероятности и математической статистике». Наука . 260 (5111): 1170–1173. дои : 10.1126/science.260.5111.1170. ISSN  0036-8075. ПМИД  17806355.
11. Вороной 1908а и Вороной 1908б.
12. де Берг, Марк ; ван Кревелд, Марк ; Овермарс, Марк ; Шварцкопф, Отфрид (2008). Вычислительная геометрия (Третье изд.). Спрингер-Верлаг . ISBN 978-3-540-77974-2.7.4. Диаграммы Вороного для дальней точки. Содержит описание алгоритма.
13. Скюм, Свен (18 февраля 1991 г.). «Простой алгоритм вычисления наименьшего охватывающего круга». Письма об обработке информации . 37 (3): 121–125. дои : 10.1016/0020-0190(91)90030-Л., содержит простой алгоритм для вычисления диаграммы Вороного в самой дальней точке.
14. Бидль, Тереза ; Гримм, Карстен; Палиос, Леонид; Шевчук, Джонатан ; Вердоншот, Сандер (2016). «Реализация диаграмм Вороного в самой дальней точке». Материалы 28-й Канадской конференции по вычислительной геометрии (CCCG, 2016) .
15. Эдельсбруннер, Герберт (2012) [1987]. «13.6 Силовые диаграммы». Алгоритмы в комбинаторной геометрии . Монографии EATCS по теоретической информатике. Том. 10. Шпрингер-Верлаг. стр. 327–328. ISBN 9783642615689.
16. Сунил Арья, Сунил; Маламатос, Теохарис; Маунт, Дэвид М. (2002). «Экономичные приближенные диаграммы Вороного». Материалы тридцать четвертого ежегодного симпозиума ACM по теории вычислений . стр. 721–730. дои : 10.1145/509907.510011. ISBN 1581134959. S2CID  1727373.
17. Хёльшер, Тонио; Кремкер, Сюзанна; Мара, Юбер (2020). «Der Kopf Sabouroff в Берлине: Zwischen Archäologischer Beobachtung und Geometrischer Vermessung». Gedenkschrift für Georgios Despinis (на немецком языке). Афины, Греция: Музей Бенаки .
18. Ячейки Вороного и геодезические расстояния — глава Сабурова на YouTube . Анализ с использованием программной платформы GigaMesh , как описано Hölscher et al. ср. doi:10.11588/heidok.00027985.
19. Лейвер, Майкл; Сердженти, Эрнест (2012). Партийная конкуренция: агентная модель . Принстон: Издательство Принстонского университета. ISBN 978-0-691-13903-6.
20. Бок, Мартин; Тьяги, Амит Кумар; Крефт, Ян-Ульрих; Альт, Вольфганг (2009). «Обобщенная тесселяция Вороного как модель двумерной динамики клеточной ткани». Бюллетень математической биологии . 72 (7): 1696–1731. arXiv : 0901.4469v1 . Бибкод : 2009arXiv0901.4469B. doi : 10.1007/s11538-009-9498-3. PMID  20082148. S2CID  16074264.
21. Хуэй Ли (2012). Баскурт, Атилла М; Ситник, Роберт (ред.). «Пространственное моделирование микроархитектуры кости». Обработка трехмерных изображений (3Dip) и приложения II . 8290 : 82900П. Бибкод : 2012SPIE.8290E..0PL. дои : 10.1117/12.907371. S2CID  1505014.
22. Санчес-Гутьеррес, Д.; Тозлуоглу, М.; Барри, доктор юридических наук; Паскаль, А.; Мао, Ю.; Эскудеро, LM (04 января 2016 г.). «Фундаментальные физические клеточные ограничения стимулируют самоорганизацию тканей». Журнал ЭМБО . 35 (1): 77–88. дои : 10.15252/embj.201592374. ПМК 4718000 . ПМИД  26598531. 
23. Файнштейн, Джозеф; Ши, Вэньтао; Рамануджам, Дж.; Брылинский, Михал (2021). «Бионой: представление участков связывания лигандов в белках на основе диаграмм Вороного для приложений машинного обучения». В Балланте, Флавио (ред.). Белково-лигандные взаимодействия и дизайн лекарств. Методы молекулярной биологии. Том. 2266. Нью-Йорк, штат Нью-Йорк: Springer US. стр. 299–312. дои : 10.1007/978-1-0716-1209-5_17. ISBN 978-1-0716-1209-5. PMID  33759134. S2CID  232338911 . Проверено 23 апреля 2021 г.
24. Спрингель, Волкер (2010). «E Pur si Muove: Галилеево-инвариантное космологическое гидродинамическое моделирование на движущейся сетке». МНРАС . 401 (2): 791–851. arXiv : 0901.4107 . Бибкод : 2010MNRAS.401..791S. дои : 10.1111/j.1365-2966.2009.15715.x. S2CID  119241866.
25. Касим, Мухаммад Фирмансия (01 января 2017 г.). «Количественная теневая и протонная радиография для модуляций большой интенсивности». Физический обзор E . 95 (2): 023306. arXiv : 1607.04179 . Бибкод : 2017PhRvE..95b3306K. doi : 10.1103/PhysRevE.95.023306. PMID  28297858. S2CID  13326345.
26. Стивен Джонсон (19 октября 2006 г.). Карта призраков: история самой ужасающей эпидемии Лондона — и как она изменила науку, города и современный мир. Издательская группа «Пингвин». п. 187. ИСБН 978-1-101-15853-1. Проверено 16 октября 2017 г.
27. Малхеран, Пенсильвания; Блэкман, Дж. А. (1996). «Зоны захвата и масштабирование при росте однородных тонких пленок». Физический обзор B . 53 (15): 10261–7. Бибкод : 1996PhRvB..5310261M. doi : 10.1103/PhysRevB.53.10261. ПМИД  9982595.
28. Пимпинелли, Альберто; Тумбек, Левент; Винклер, Адольф (2014). «Масштабирование и равенство показателей при островковом зарождении: новые результаты и применение к органическим пленкам». Журнал физической химии . 5 (6): 995–8. дои : 10.1021/jz500282t. ПМЦ 3962253 . ПМИД  24660052. 
29. Фанфони, М.; Плачиди, Э.; Арципрет, Ф.; Орсини, Э.; Пателла, Ф.; Бальзаротти, А. (2007). «Внезапное зарождение и масштабная инвариантность квантовых точек InAs на GaAs». Физический обзор B . 75 (24): 245312. Бибкод : 2007PhRvB..75x5312F. doi : 10.1103/PhysRevB.75.245312. ISSN  1098-0121. S2CID  120017577.
30. Миямото, Сатору; Мутанаббир, Усама; Халлер, Юджин Э.; Ито, Кохей М. (2009). «Пространственная корреляция самоорганизующихся изотопно чистых наноостровков Ge/Si (001)». Физический обзор B . 79 (165415): 165415. Бибкод : 2009PhRvB..79p5415M. doi : 10.1103/PhysRevB.79.165415. ISSN  1098-0121. S2CID  13719907.
31. Лёбл, Матиас К.; Чжай, Лян; Ян, Ян-Филипп; Ритцманн, Джулиан; Хо, Юнхэн; Вик, Андреас Д.; Шмидт, Оливер Г.; Людвиг, Арне; Растелли, Армандо; Уорбертон, Ричард Дж. (3 октября 2019 г.). «Корреляция между оптическими свойствами и площадью ячейки Вороного квантовых точек». Физический обзор B . 100 (15): 155402. arXiv : 1902.10145 . Бибкод : 2019PhRvB.100o5402L. doi : 10.1103/physrevb.100.155402. ISSN  2469-9950. S2CID  119443529.
32. "КУЛЬТУРНЫЙ УЧАСТОК ГОЛД-КОСТ" . АРМ Архитектура. Архивировано из оригинала 7 июля 2016 г. Проверено 28 апреля 2014 г.
33. Лопес, К.; Чжао, К.-Л.; Магниол, С; Чиабо, Н.; Леклерк, Л. (28 февраля 2019 г.). «Микроскопическое моделирование движения грузовых автомобилей при парковке как мера управления зоной погрузки грузов». Устойчивость . 11 (5), 1276.
34. Сингх, К.; Садеги, Ф.; Корренс, М.; Бласс, Т. (декабрь 2019 г.). «Подход, основанный на микроструктуре, к моделированию влияния шероховатости поверхности на усталость при растяжении». Международный журнал усталости . 129 : 105229. doi : 10.1016/j.ijfatigue.2019.105229. S2CID  202213370.
35. Ню, Ханлин; Савварис, Ал; Цурдос, Антониос; Цзи, Зе (2019). «Алгоритм планирования пути для беспилотных надводных транспортных средств на основе дорожной карты Вороного» (PDF) . Журнал навигации . 72 (4): 850–874. дои : 10.1017/S0373463318001005. S2CID  67908628.
36. Кортес, Дж.; Мартинес, С.; Каратас, Т.; Булло, Ф. (апрель 2004 г.). «Контроль покрытия мобильных сенсорных сетей». Транзакции IEEE по робототехнике и автоматизации . 20 (2): 243–255. дои : 10.1109/TRA.2004.824698. ISSN  2374-958Х. S2CID  2022860.
37. Теруэль, Энрике; Арагеш, Росарио; Лопес-Николас, Гонсало (апрель 2021 г.). «Практический метод равномерного покрытия роем динамической области». Письма IEEE по робототехнике и автоматизации . 6 (2): 1359–1366. дои : 10.1109/LRA.2021.3057568. ISSN  2377-3766. S2CID  232071627.
38. Митчелл, Том М. (1997). Машинное обучение (международное изд.). МакГроу-Хилл. п. 233. ИСБН 978-0-07-042807-2.
39. Шенвай, Танушри (18 ноября 2021 г.). «Новая методика глубокого обучения, которая восстанавливает глобальные поля без использования организованных данных датчиков». МаркТехПост . Проверено 5 декабря 2021 г.
40. Архивировано в Ghostarchive и Wayback Machine: «Марк ДиМарко: Алгоритмы пользовательского интерфейса [JSConf2014]» - через www.youtube.com.
41. «Найди мою школу» . Государственный департамент образования штата Виктория . Проверено 25 июля 2023 г.
42. Хариди, Рич (6 сентября 2017 г.). «Архитектор, ставший кондитером, готовит аппетитные геометрические торты, напечатанные на 3D-принтере» . Новый Атлас .
43. Жун, Годун; Тан, Тиоу Сенг (2006). «Переполнение графического процессора приложениями к диаграмме Вороного и дистанционному преобразованию» (PDF) . В Олано, Марк; Секен, Карло Х. (ред.). Материалы симпозиума по интерактивной 3D-графике 2006 г., SI3D 2006, 14–17 марта 2006 г., Редвуд-Сити, Калифорния, США . АКМ. стр. 109–116. дои : 10.1145/1111411.1111431.
44. "Шедертой".

Рекомендации

• Ауренхаммер, Франц ; Кляйн, Рольф; Ли, Дер-Цай (2013). Диаграммы Вороного и триангуляции Делоне . Всемирная научная. ISBN 978-9814447638.
• Бойер, Адриан (1981). «Вычисление мозаики Дирихле». Вычислить. Дж. 24 (2): 162–166. дои : 10.1093/comjnl/24.2.162 .
• де Берг, Марк; ван Кревелд, Марк; Овермарс, Марк ; Шварцкопф, Отфрид (2000). «7. Диаграммы Вороного». Вычислительная геометрия (2-е исправленное изд.). Спрингер. стр. 47–163. ISBN 978-3-540-65620-3. Включает описание алгоритма Фортуны.
• Кляйн, Рольф (1988). «Абстрактные диаграммы Вороного и их приложения: Расширенный реферат». Вычислительная геометрия и ее приложения . Конспекты лекций по информатике . Том. 333. Спрингер. стр. 148–157. дои : 10.1007/3-540-50335-8_31. ISBN 978-3-540-52055-9.
• Лежен Дирихле, Ж. (1850). «Über die Reduktion der Positive Squaretischen Formen mit Drei unbestimmten ganzen Zahlen». Журнал для королевы и математики . 1850 (40): 209–227. дои : 10.1515/crll.1850.40.209. S2CID  199546675.
• Окабе, Ацуюки; Бутс, Барри; Сугихара, Кокичи ; Чиу, Сунг Нок (2000). Пространственные замощения - концепции и применение диаграмм Вороного (2-е изд.). Уайли. ISBN 0-471-98635-6.
• Рим, Дэниел (2009). «Алгоритм вычисления диаграмм Вороного общих генераторов в общих нормированных пространствах». Материалы шестого международного симпозиума по диаграммам Вороного в науке и технике (ISVD 2009) . стр. 144–152. дои :10.1109/ИСВД.2009.23. ISBN 978-1-4244-4769-5.
• Рим, Дэниел (2011). «Геометрическая устойчивость диаграмм Вороного относительно небольших изменений узлов». Материалы двадцать седьмого ежегодного симпозиума по вычислительной геометрии . стр. 254–263. arXiv : 1103.4125 . Бибкод : 2011arXiv1103.4125R. дои : 10.1145/1998196.1998234. ISBN 9781450306829. S2CID  14639512.
• Тиссен, Альфред Х. (июль 1911 г.). «Среднее количество осадков на больших территориях». Ежемесячный обзор погоды . Американское метеорологическое общество. 39 (7): 1082–1089. Бибкод : 1911MWRv...39R1082T. doi : 10.1175/1520-0493(1911)39<1082b:pafla>2.0.co;2 .
• Вороной, Жорж (1908а). «Новые приложения непрерывных параметров в теории квадратичных форм. Premier mémoire. Sur quelques proprietés des formes положительные парфаиты» (PDF) . Журнал для королевы и математики . 1908 (133): 97–178. дои : 10.1515/crll.1908.133.97. S2CID  116775758.
• Вороной, Жорж (1908b). «Новые приложения непрерывных параметров в теории квадратных форм. Deuxième mémoire. Recherches sur les parallélloèdres primitifs» (PDF) . Журнал для королевы и математики . 1908 (134): 198–287. дои : 10.1515/crll.1908.134.198. S2CID  118441072.
• Уотсон, Дэвид Ф. (1981). «Вычисление n-мерной мозаики Делоне с применением к многогранникам Вороного». Вычислить. Дж. 24 (2): 167–172. дои : 10.1093/comjnl/24.2.167 .

Внешние ссылки

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