Диаграмма Вороного
В математике диаграмма Вороного — это разбиение плоскости на области , близкие к каждому из заданного набора объектов. Его также можно классифицировать как тесселяцию . В простейшем случае эти объекты представляют собой конечное число точек на плоскости (называемых семенами, узлами или генераторами). Для каждого семени существует соответствующая область , называемая ячейкой Вороного , состоящая из всех точек плоскости, находящихся ближе к этому семени, чем к любому другому. Диаграмма Вороного набора точек двойственна этого набора триангуляции Делоне .
Диаграмма Вороного названа в честь математика Георгия Вороного , а также называется мозаикой Вороного , разложением Вороного , разбиением Вороного или мозаикой Дирихле (в честь Питера Густава Лежена Дирихле ). Ячейки Вороного также известны как многоугольники Тиссена , в честь Альфреда Х. Тиссена . [ 1 ] [ 2 ] [ 3 ] Диаграммы Вороного имеют практическое и теоретическое применение во многих областях, в основном в науке и технике , а также в изобразительном искусстве . [ 4 ] [ 5 ]
Самый простой случай
[ редактировать ]В простейшем случае, показанном на первой картинке, нам дан конечный набор точек в евклидовой плоскости . В этом случае каждый сайт - одна из этих заданных точек, а соответствующая ей ячейка Вороного состоит из каждой точки евклидовой плоскости, для которой ближайший объект: расстояние до меньше или равно минимальному расстоянию до любого другого объекта . Для еще одного сайта , точки, которые ближе к чем , или одинаково удаленные, образуют замкнутое полупространство , граница которого является серединным перпендикуляром отрезка прямой . Клетка это пересечение всего этого полупространства, и, следовательно, это выпуклый многоугольник . [ 6 ] Когда две ячейки на диаграмме Вороного имеют общую границу, это отрезок , луч или линия, состоящая из всех точек плоскости, которые равноудалены от двух ближайших к ним точек. Вершины . диаграммы, где встречаются три или более из этих границ, представляют собой точки, имеющие три или более одинаково удаленных ближайших узла
Формальное определение
[ редактировать ]Позволять быть метрическим пространством с функцией расстояния . Позволять — набор индексов и пусть быть кортежем (индексированной коллекцией) непустых подмножеств (сайтов) в пространстве . Ячейка Вороного, или область Вороного, , связанный с сайтом это совокупность всех точек расстояние до которого не больше, чем их расстояние до других сайтов , где отличается ли какой-либо индекс от . Другими словами, если обозначает расстояние между точкой и подмножество , затем
Диаграмма Вороного — это просто набор ячеек. . В принципе, некоторые сайты могут пересекаться и даже совпадать (ниже описано применение сайтов, представляющих магазины), но обычно они считаются непересекающимися. Кроме того, в определении допускается бесконечное количество узлов (эта настройка имеет приложения в геометрии чисел и кристаллографии ), но опять же во многих случаях рассматривается только конечное число узлов.
В частном случае, когда пространство представляет собой конечномерное евклидово пространство , каждый узел является точкой, точек конечно много и все они различны, тогда ячейки Вороного являются выпуклыми многогранниками , и их можно представить комбинаторно с помощью их вершины, стороны, двумерные грани и т. д. Иногда индуцированную комбинаторную структуру называют диаграммой Вороного. Однако в целом ячейки Вороного могут быть невыпуклыми и даже не связными.
В обычном евклидовом пространстве мы можем переписать формальное определение в обычных терминах. Каждый полигон Вороного связан с генераторной точкой . Позволять — множество всех точек евклидова пространства. Позволять быть точкой, которая генерирует область Вороного , который генерирует , и который генерирует , и так далее. Тогда, как выразились Тран и др ., [ 7 ] «все местоположения в многоугольнике Вороного находятся ближе к образующей точке этого многоугольника, чем любая другая образующая точка на диаграмме Вороного в евклидовой плоскости».
Иллюстрация
[ редактировать ]В качестве простой иллюстрации рассмотрим группу магазинов в городе. Предположим, мы хотим оценить количество покупателей данного магазина. При прочих равных условиях (цена, продукция, качество обслуживания и т. д.) разумно предположить, что покупатели выбирают предпочитаемый магазин просто по соображениям расстояния: они пойдут в ближайший к ним магазин. В этом случае ячейка Вороного данного магазина можно использовать для приблизительной оценки количества потенциальных покупателей, посещающих этот магазин (который моделируется точкой в нашем городе).
Для большинства городов расстояние между точками можно измерить с помощью привычного нам метода. Евклидово расстояние :
или Манхэттенское расстояние :
- .
Соответствующие диаграммы Вороного выглядят по-разному для разных метрик расстояния.
Характеристики
[ редактировать ]- Двойственный граф диаграммы Вороного (в случае евклидова пространства с точечными узлами) соответствует триангуляции Делоне для того же набора точек.
- Ближайшая пара точек соответствует двум соседним ячейкам диаграммы Вороного.
- Предположим, что задана евклидова плоскость и задан дискретный набор точек. Тогда две точки множества смежны на выпуклой оболочке тогда и только тогда, когда их ячейки Вороного имеют бесконечно длинную сторону.
- Если пространство является нормированным пространством и расстояние до каждого узла достигнуто (например, когда узел представляет собой компакт или замкнутый шар), то каждую ячейку Вороного можно представить как объединение отрезков, исходящих из узлов. [ 8 ] Как показано там, это свойство не обязательно сохраняется, если расстояние не достигнуто.
- При относительно общих условиях (пространство представляет собой, возможно, бесконечномерное равномерно выпуклое пространство , может быть бесконечно много узлов общего вида и т. д.) ячейки Вороного обладают определенным свойством устойчивости: небольшим изменением формы узлов, напр. , изменение, вызванное некоторой трансляцией или искажением, приводит к небольшому изменению формы ячеек Вороного. В этом заключается геометрическая устойчивость диаграмм Вороного. [ 9 ] Как там показано, это свойство, вообще говоря, не выполняется, даже если пространство двумерно (но неравномерно выпукло и, в частности, неевклидово) и узлы являются точками.
История и исследования
[ редактировать ]Неофициальное использование диаграмм Вороного восходит к Декарту в 1644 году. [ 10 ] Питер Густав Лежен Дирихле использовал двумерные и трехмерные диаграммы Вороного в своем исследовании квадратичных форм в 1850 году. Британский врач Джон Сноу использовал диаграмму, подобную Вороному, в 1854 году, чтобы проиллюстрировать, как большинство людей, умерших во время вспышки холеры на Брод-стрит, жили ближе к зараженному насосу на Брод-стрит, чем к любому другому водяному насосу.
Диаграммы Вороного названы в честь Георгия Феодосиевича Вороного, который определил и изучил общий n -мерный случай в 1908 году. [ 11 ] Диаграммы Вороного, которые используются в геофизике и метеорологии для анализа пространственно распределенных данных, называются полигонами Тиссена в честь американского метеоролога Альфреда Х. Тиссена , который использовал их для оценки количества осадков на основе разрозненных измерений в 1911 году. Другие эквивалентные названия для этой концепции (или отдельных важных случаев it): многогранники Вороного, многоугольники Вороного, область(и) влияния, разложение Вороного, мозаика(ы) Вороного, мозаика(ы) Дирихле.
Примеры
[ редактировать ]Мозаики Вороного из регулярных решеток точек в двух или трех измерениях порождают многие знакомые мозаики.
- 2D-решетка представляет собой неправильную сотовую мозаику с одинаковыми шестиугольниками с точечной симметрией; в случае правильной треугольной решетки она правильна; в случае прямоугольной решетки шестиугольники сводятся к прямоугольникам в строках и столбцах; квадратная ; решетка дает правильную мозаику квадратов обратите внимание, что прямоугольники и квадраты также могут быть созданы другими решетками (например, решетка, определяемая векторами (1,0) и (1/2,1/2), дает квадраты).
- Простая кубическая решетка дает кубические соты .
- Шестиугольная плотноупакованная решетка дает замощение пространства трапезо-ромбическими додекаэдрами .
- Гробоцентрированная кубическая решетка дает замощение пространства ромбическими додекаэдрами .
- Объемноцентрированная кубическая решетка дает мозаику пространства усеченными октаэдрами .
- Параллельные плоскости с правильными треугольными решетками, совмещенными с центрами друг друга, образуют шестиугольные призматические соты .
- Определенные объемноцентрированные тетрагональные решетки образуют мозаику пространства с ромбо-шестиугольными додекаэдрами .
Определенные объемноцентрированные тетрагональные решетки образуют мозаику пространства с ромбо-шестиугольными додекаэдрами .
Для набора точек ( x , y ) с x в дискретном множестве X и y в дискретном множестве Y мы получаем прямоугольные плитки с точками не обязательно в их центрах.
Диаграммы Вороного высшего порядка
[ редактировать ]Хотя нормальная ячейка Вороного определяется как набор точек, ближайших к одной точке в S , ячейка Вороного n -го порядка определяется как набор точек, имеющих конкретный набор из n точек в S в качестве n ближайших соседей. Диаграммы Вороного высшего порядка также подразделяют пространство.
Диаграммы Вороного высшего порядка можно генерировать рекурсивно. Чтобы сгенерировать n й -порядок диаграммы Вороного из множества S , начните с ( n − 1) й -порядка и замените каждую ячейку, порожденную X = { x 1 , x 2 , ..., x n −1 }, диаграммой Вороного, порожденной на множестве S − X .
Диаграмма Вороного для самой дальней точки
[ редактировать ]Для набора из n точек ( n − 1) й Диаграмма Вороного -порядка называется диаграммой Вороного в самой дальней точке.
Для данного набора точек S = { p 1 , p 2 , ..., p n } диаграмма Вороного самой дальней точки делит плоскость на ячейки, в которых одна и та же точка P является самой дальней точкой. Точка P точки тогда и только тогда, когда она является вершиной выпуклой оболочки P имеет ячейку в диаграмме Вороного самой дальней . Пусть H = { h 1 , h 2 , ..., 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 ]
Диаграммы Вороного также связаны с другими геометрическими структурами, такими как медиальная ось (которая нашла применение в сегментации изображений, оптическом распознавании символов и других вычислительных приложениях), прямой скелет и диаграммы зон .
Приложения
[ редактировать ]Метеорология/Гидрология
[ редактировать ]Он используется в метеорологии и инженерной гидрологии для определения весов данных об осадках на станциях по территории (водоразделу). Точками, образующими полигоны, являются различные станции, записывающие данные об осадках. К линии, соединяющей любые две станции, проводят биссектрисы. Это приводит к образованию полигонов вокруг станций. Район точка касания станции известна как зона влияния станции. Среднее количество осадков рассчитывается по формуле
Гуманитарные и социальные науки
[ редактировать ]- В классической археологии , особенно в истории искусства , симметрия голов статуй анализируется, чтобы определить тип статуи, которой могла принадлежать отрубленная голова. Примером использования ячеек Вороного была идентификация головы Сабурова , в которой использовалась полигональная сетка высокого разрешения . [ 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 ] Подход Вороного также применяется при оценке округлости/ круглости при оценке набора данных с координатно-измерительной машины .
- Нули повторных производных рациональной функции на комплексной плоскости накапливаются на краях диаграммы Вороного множества полюсов ( теорема Пойа о графстве [ 38 ] ).
Информатика
[ редактировать ]- В сетях диаграммы Вороного могут быть использованы для определения пропускной способности беспроводной сети .
- В компьютерной графике диаграммы Вороного используются для расчета трехмерных геометрических моделей разрушения/разрыва. Он также используется для процедурного создания органических текстур или текстур, похожих на лаву.
- В автономной навигации роботов диаграммы Вороного используются для поиска четких маршрутов. Если точки являются препятствиями, то ребрами графа будут маршруты, наиболее удаленные от препятствий (и теоретически от любых столкновений).
- В машинном обучении диаграммы Вороного используются для классификации 1-NN . [ 39 ]
- При глобальной реконструкции сцены, в том числе со случайными местоположениями датчиков и нестационарным следом, геофизическими данными и трехмерными данными турбулентности, тесселяции Вороного используются с глубоким обучением . [ 40 ]
- При разработке пользовательского интерфейса шаблоны Вороного можно использовать для вычисления наилучшего состояния наведения для заданной точки. [ 41 ]
Гражданское право и планирование
[ редактировать ]- В Мельбурне учащиеся государственных школ всегда имеют право посещать ближайшую к месту их проживания начальную или среднюю школу, если измерять расстояние по прямой. Таким образом, карта школьных зон представляет собой диаграмму Вороного. [ 42 ]
Пекарня
[ редактировать ]- Украинский кондитер Динара Касько использует математические принципы диаграммы Вороного для создания силиконовых форм, изготовленных на 3D-принтере, для придания формы своим оригинальным тортам. [ 43 ]
Алгоритмы
[ редактировать ]Известно несколько эффективных алгоритмов построения диаграмм Вороного либо напрямую (как сама диаграмма), либо косвенно, начиная с триангуляции Делоне и затем получая ее двойственную. К прямым алгоритмам относится алгоритм Фортуны — алгоритм O ( n log( n )) для генерации диаграммы Вороного из набора точек на плоскости. Алгоритм Бойера–Ватсона , от O ( n log( n )) до O ( n 2 ) алгоритм построения триангуляции Делоне в любом количестве измерений, может быть использован в косвенном алгоритме для диаграммы Вороного. Алгоритм Jump Flooding может генерировать приблизительные диаграммы Вороного за постоянное время и подходит для использования на обычном графическом оборудовании. [ 44 ] [ 45 ]
Алгоритм Ллойда и его обобщение с помощью алгоритма Линде – Бьюзо – Грея (также известного как кластеризация k-средних ) используют построение диаграмм Вороного в качестве подпрограммы. Эти методы чередуются между этапами построения диаграммы Вороного для набора исходных точек и этапами, на которых исходные точки перемещаются в новые места, которые являются более центральными внутри своих ячеек. Эти методы можно использовать в пространствах произвольной размерности для итеративной сходимости к специализированной форме диаграммы Вороного, называемой центроидальной мозаикой Вороного , где узлы перемещаются в точки, которые также являются геометрическими центрами их ячеек.
Вороной и 3D
[ редактировать ]Сетки Вороного также можно создавать в 3D.
-
Случайные точки в 3D для формирования 3D-раздела Вороного
-
3D Voronoi mesh of 25 random points
-
3D-сетка Вороного из 25 случайных точек с непрозрачностью 0,3 и точками
-
3D-сетка Вороного из 25 случайных точек частей выпуклых многогранников
См. также
[ редактировать ]Примечания
[ редактировать ]- ^ Берроу, Питер А.; Макдоннелл, Рэйчел; Макдоннелл, Рэйчел А.; Ллойд, Кристофер Д. (2015). «8.11 Ближайшие соседи: многоугольники Тиссена (Дирихле/Ворони)» . Принципы географических информационных систем . Издательство Оксфордского университета. стр. 160–. ISBN 978-0-19-874284-5 .
- ^ Лонгли, Пол А.; Гудчайлд, Майкл Ф.; Магуайр, Дэвид Дж.; Ринд, Дэвид В. (2005). «14.4.4.1 Многоугольники Тиссена» . Географические информационные системы и наука . Уайли. стр. 333–. ISBN 978-0-470-87001-3 .
- ^ Сен, Зекай (2016). «2.8.1 Многоугольники Делани, Варони и Тиссена» . Принципы пространственного моделирования в науках о Земле . Спрингер. стр. 57–. ISBN 978-3-319-41758-5 .
- ^ Ауренхаммер, Франц (1991). «Диаграммы Вороного - обзор фундаментальной геометрической структуры данных». Обзоры вычислительной техники ACM . 23 (3): 345–405. дои : 10.1145/116873.116880 . S2CID 4613674 .
- ^ Окабе, Ацуюки; Бутс, Барри; Сугихара, Кокичи; Чиу, Сунг Нок (2000). Пространственные замощения - концепции и применение диаграмм Вороного (2-е изд.). Джон Уайли. ISBN 978-0-471-98635-5 .
- ^ Бойд, Стивен; Ванденберге, Ливен (2004). Выпуклая оптимизация . Упражнение 2.9: Издательство Кембриджского университета. п. 60.
{{cite book}}
: CS1 maint: местоположение ( ссылка ) - ^ Тран, QT; Тайнар, Д.; Сафар, М. (2009). Транзакции в крупномасштабных системах, ориентированных на данные и знания . Спрингер. п. 357. ИСБН 9783642037214 .
- ^ Рим 2009 .
- ^ Рим 2011 .
- ^ Сенешаль, Марджори (21 мая 1993 г.). «Математические структуры: пространственная мозаика. Концепции и приложения диаграмм Вороного. Ацуюки Окабе, Барри Бутс и Кокичи Сугихара. Уайли, Нью-Йорк, 1992. xii, 532 стр., иллюстр. $ 89,95. Серия Уайли по вероятности и математической статистике» . Наука . 260 (5111): 1170–1173. дои : 10.1126/science.260.5111.1170 . ISSN 0036-8075 . ПМИД 17806355 .
- ^ Вороной 1908а и Вороной 1908б .
- ^ Jump up to: а б де Берг, Марк ; ван Кревелд, Марк ; Овермарс, Марк ; Шварцкопф, Отфрид (2008). Вычислительная геометрия (Третье изд.). Издательство Спрингер . ISBN 978-3-540-77974-2 . 7.4. Диаграммы Вороного для дальней точки. Содержит описание алгоритма.
- ^ Скюм, Свен (18 февраля 1991 г.). «Простой алгоритм вычисления наименьшего охватывающего круга». Письма об обработке информации . 37 (3): 121–125. дои : 10.1016/0020-0190(91)90030-L . , содержит простой алгоритм для вычисления диаграммы Вороного в самой дальней точке.
- ^ Бидль, Тереза ; Гримм, Карстен; Палиос, Леонид; Шевчук, Джонатан ; Вердоншот, Сандер (2016). «Реализация диаграмм Вороного в самой дальней точке». Материалы 28-й Канадской конференции по вычислительной геометрии (CCCG, 2016) .
- ^ Эдельсбруннер, Герберт (2012) [1987]. «13.6 Силовые диаграммы». Алгоритмы в комбинаторной геометрии . Монографии EATCS по теоретической информатике. Том. 10. Шпрингер-Верлаг. стр. 327–328. ISBN 9783642615689 .
- ^ Сунил Арья, Сунил; Маламатос, Теохарис; Маунт, Дэвид М. (2002). «Экономичные приближенные диаграммы Вороного». Материалы тридцать четвертого ежегодного симпозиума ACM по теории вычислений . стр. 721–730. дои : 10.1145/509907.510011 . ISBN 1581134959 . S2CID 1727373 .
- ^ Хёльшер, Тонио; Кремкер, Сюзанна; Мара, Юбер (2020). « Голова Сабурова в Берлине: между археологическими наблюдениями и геометрическими измерениями». Памятное издание Георгиосу Деспинису (на немецком языке). Афины, Греция: Музей Бенаки .
- ^ Ячейки Вороного и геодезические расстояния — глава Сабурова на YouTube . Анализ с использованием программной платформы GigaMesh, как описано Hölscher et al. ср. дои:10.11588/heidok.00027985 .
- ^ Лейвер, Майкл; Сердженти, Эрнест (2012). Партийная конкуренция: агентная модель . Принстон: Издательство Принстонского университета. ISBN 978-0-691-13903-6 .
- ^ Бок, Мартин; Тьяги, Амит Кумар; Крефт, Ян-Ульрих; Альт, Вольфганг (2009). «Обобщенная тесселяция Вороного как модель двумерной динамики клеточной ткани». Бюллетень математической биологии . 72 (7): 1696–1731. arXiv : 0901.4469v1 . Бибкод : 2009arXiv0901.4469B . дои : 10.1007/s11538-009-9498-3 . ПМИД 20082148 . S2CID 16074264 .
- ^ Хуэй Ли (2012). Баскурт, Атилла М; Ситник, Роберт (ред.). «Пространственное моделирование микроархитектуры кости». Обработка трехмерных изображений (3Dip) и приложения II . 8290 : 82900П. Бибкод : 2012SPIE.8290E..0PL . дои : 10.1117/12.907371 . S2CID 1505014 .
- ^ Jump up to: а б Санчес-Гутьеррес, Д.; Тозлуоглу, М.; Барри, доктор юридических наук; Паскаль, А.; Мао, Ю.; Эскудеро, LM (04 января 2016 г.). «Фундаментальные физические клеточные ограничения стимулируют самоорганизацию тканей» . Журнал ЭМБО . 35 (1): 77–88. дои : 10.15252/embj.201592374 . ПМК 4718000 . ПМИД 26598531 .
- ^ Файнштейн, Джозеф; Ши, Вэньтао; Рамануджам, Дж.; Брылинский, Михал (2021). «Бионой: представление участков связывания лигандов в белках на основе диаграмм Вороного для приложений машинного обучения». В Балланте, Флавио (ред.). Белково-лигандные взаимодействия и дизайн лекарств . Методы молекулярной биологии. Том. 2266. Нью-Йорк, штат Нью-Йорк: Springer US. стр. 299–312. дои : 10.1007/978-1-0716-1209-5_17 . ISBN 978-1-0716-1209-5 . ПМИД 33759134 . S2CID 232338911 . Проверено 23 апреля 2021 г.
- ^ Спрингель, Волкер (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 .
- ^ Касим, Мухаммад Фирмансия (01 января 2017 г.). «Количественная теневая и протонная радиография для модуляций большой интенсивности». Физический обзор E . 95 (2): 023306. arXiv : 1607.04179 . Бибкод : 2017PhRvE..95b3306K . дои : 10.1103/PhysRevE.95.023306 . ПМИД 28297858 . S2CID 13326345 .
- ^ Стивен Джонсон (19 октября 2006 г.). Карта призраков: история самой ужасающей эпидемии в Лондоне — и как она изменила науку, города и современный мир . Издательская группа «Пингвин». п. 187. ИСБН 978-1-101-15853-1 . Проверено 16 октября 2017 г.
- ^ Малхеран, Пенсильвания; Блэкман, Дж. А. (1996). «Зоны захвата и масштабирование при росте однородных тонких пленок». Физический обзор B . 53 (15): 10261–7. Бибкод : 1996PhRvB..5310261M . дои : 10.1103/PhysRevB.53.10261 . ПМИД 9982595 .
- ^ Пимпинелли, Альберто; Тумбек, Левент; Винклер, Адольф (2014). «Масштабирование и равенство показателей при островковом зарождении: новые результаты и применение к органическим пленкам» . Журнал физической химии . 5 (6): 995–8. дои : 10.1021/jz500282t . ПМЦ 3962253 . ПМИД 24660052 .
- ^ Фанфони, М.; Плачиди, Э.; Протоиерей Ф.; Орсини, Э.; Пателла, Ф.; Бальзаротти, А. (2007). «Внезапное зарождение и масштабная инвариантность квантовых точек InAs на GaAs». Физический обзор Б. 75 (24): 245312. Бибкод : 2007PhRvB..75x5312F . дои : 10.1103/PhysRevB.75.245312 . ISSN 1098-0121 . S2CID 120017577 .
- ^ Миямото, Сатору; Мутанаббир, Усама; Халлер, Юджин Э.; Ито, Кохей М. (2009). «Пространственная корреляция самоорганизующихся изотопно чистых наноостровков Ge/Si (001)». Физический обзор B . 79 (165415): 165415. Бибкод : 2009PhRvB..79p5415M . дои : 10.1103/PhysRevB.79.165415 . ISSN 1098-0121 . S2CID 13719907 .
- ^ Лёбл, Маттиас К.; Чжай, Лян; Ян, Ян-Филипп; Ритцманн, Джулиан; Хо, Юнхэн; Вик, Андреас Д.; Шмидт, Оливер Г.; Людвиг, Арне; Растелли, Армандо; Уорбертон, Ричард Дж. (3 октября 2019 г.). «Корреляция между оптическими свойствами и площадью ячейки Вороного квантовых точек». Физический обзор B . 100 (15): 155402. arXiv : 1902.10145 . Бибкод : 2019PhRvB.100o5402L . дои : 10.1103/physrevb.100.155402 . ISSN 2469-9950 . S2CID 119443529 .
- ^ «КУЛЬТУРНЫЙ УЧАСТОК ГОЛД-КОСТ» . АРМ Архитектура. Архивировано из оригинала 7 июля 2016 г. Проверено 28 апреля 2014 г.
- ^ Лопес, К.; Чжао, К.-Л.; Магниол, С; Чиабо, Н.; Леклерк, Л. (28 февраля 2019 г.). «Микроскопическое моделирование движения грузовых автомобилей при парковке как мера управления зоной погрузки грузов» . Устойчивость . 11 (5), 1276.
- ^ Сингх, К.; Садеги, Ф.; Корренс, М.; Бласс, Т. (декабрь 2019 г.). «Подход, основанный на микроструктуре, к моделированию влияния шероховатости поверхности на усталость при растяжении» . Международный журнал усталости . 129 : 105229. doi : 10.1016/j.ijfatigue.2019.105229 . S2CID 202213370 .
- ^ Ню, Ханлин; Савварис, Ал; Цурдос, Антониос; Цзи, Зе (2019). «Алгоритм планирования пути для беспилотных надводных транспортных средств на основе дорожной карты Вороного» (PDF) . Журнал навигации . 72 (4): 850–874. дои : 10.1017/S0373463318001005 . S2CID 67908628 .
- ^ Кортес, Дж.; Мартинес, С.; Каратас, Т.; Булло, Ф. (апрель 2004 г.). «Контроль покрытия мобильных сенсорных сетей» . Транзакции IEEE по робототехнике и автоматизации . 20 (2): 243–255. дои : 10.1109/TRA.2004.824698 . ISSN 2374-958X . S2CID 2022860 .
- ^ Теруэль, Энрике; Арагес, Росарио; Лопес-Николас, Гонсало (апрель 2021 г.). «Практический метод равномерного покрытия роем динамической области» . Письма IEEE по робототехнике и автоматизации . 6 (2): 1359–1366. дои : 10.1109/LRA.2021.3057568 . ISSN 2377-3766 . S2CID 232071627 .
- ^ Полиа, Г. О нулях производных функции и ее аналитическом характере. Бюллетень AMS, том 49, выпуск 3, 178–191, 1943 г.
- ^ Митчелл, Том М. (1997). Машинное обучение (международное изд.). МакГроу-Хилл. п. 233 . ISBN 978-0-07-042807-2 .
- ^ Шенвай, Танушри (18 ноября 2021 г.). «Новая методика глубокого обучения, которая восстанавливает глобальные поля без использования организованных данных датчиков» . МаркТехПост . Проверено 5 декабря 2021 г.
- ^ Архивировано в Ghostarchive и Wayback Machine : «Марк ДиМарко: алгоритмы пользовательского интерфейса [JSConf2014]» – через www.youtube.com.
- ^ «Найди мою школу» . Государственный департамент образования штата Виктория . Проверено 25 июля 2023 г.
- ^ Хариди, Рич (6 сентября 2017 г.). «Архитектор, ставший кондитером, готовит аппетитные геометрические торты, напечатанные на 3D-принтере» . Новый Атлас .
- ^ Ронг, Годун; Тан, Тиоу Сенг (2006). «Переполнение графического процессора приложениями к диаграмме Вороного и дистанционному преобразованию» (PDF) . В Олано, Марк; Секин, Карло Х. (ред.). Материалы симпозиума 2006 г. по интерактивной 3D-графике, SI3D 2006, 14–17 марта 2006 г., Редвуд-Сити, Калифорния, США . АКМ. стр. 109–116. дои : 10.1145/1111411.1111431 . ISBN 1-59593-295-Х .
- ^ «Шедертой» .
Ссылки
[ редактировать ]- Ауренхаммер, Франц ; Кляйн, Рольф; Ли, Дер-Цай (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). «О приведении положительных квадратичных форм с тремя неопределенными целыми числами». Журнал чистой и прикладной математики . 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а). «Новые применения непрерывных параметров в теории квадратичных форм. Первая диссертация. О некоторых свойствах совершенных положительных квадратичных форм» (PDF) . Журнал для королевы и математики . 1908 (133): 97–178. дои : 10.1515/crll.1908.133.97 . S2CID 116775758 .
- Вороной, Жорж (1908b). «Новые применения непрерывных параметров в теории квадратичных форм. Вторая диссертация. Исследование примитивных параллелоэдров» (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, которая создает диаграмму Вороного с использованием модели степного пожара.