Введение

Тип разбиения плоскости

В математике диаграмма Вороного – это разбиение плоскости на области, близкие к каждому из заданного набора объектов. Её также можно классифицировать как тесселяцию. В самом простом случае эти объекты – это лишь конечное число точек на плоскости (называемых семенами, сайтами или генераторами). Для каждого семени существует соответствующая область, называемая ячейкой Вороного, состоящая из всех точек плоскости, более близких к этому семени, чем к любому другому. Диаграмма Вороного для набора точек двойственна триангуляции Делоне этого набора. Диаграмма Вороного названа в честь математика Георгия Вороного и также называется тесселяцией Вороного, разложением Вороного, разбиением Вороного или тесселяцией Дирихле (по имени Питера Густава Лежена Дирихле). Ячейки Вороного также известны как полигоны Тиссена, в честь Альфреда Х. Тиссена. Диаграммы Вороного имеют практическое и теоретическое применение во многих областях, главным образом в науке и технике, но также и в изобразительном искусстве.

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

В самом простом случае, показанном на первом рисунке, задается конечное множество точек в евклидовой плоскости. В этом случае каждая точка является одной из заданных точек, а соответствующая ячейка Вороного состоит из всех точек евклидовой плоскости, для которых эта точка является ближайшей: расстояние до неё меньше или равно минимальному расстоянию до любой другой точки. Для любой другой точки, точки, которые находятся ближе к ней, чем к другой точке, или равноудалены от них, образуют замкнутое полупространство, границей которого является серединный перпендикуляр отрезка прямой. Ячейка является пересечением всех этих полупространств и, следовательно, представляет собой выпуклый многоугольник. Когда две ячейки на диаграмме Вороного имеют общую границу, это отрезок прямой, луч или прямая, состоящая из всех точек плоскости, равноудаленных от двух ближайших точек. Вершины диаграммы, где пересекаются три или более таких границ, – это точки, имеющие три или более равноудаленных ближайших точек.

Формальное определение

Пусть – метрическое пространство с функцией расстояния. Пусть – множество индексов и пусть – кортеж (индексированная коллекция) непустых подмножеств (сайтов) в пространстве. Вороновская ячейка, или Вороновская область, , связанная с сайтом , представляет собой множество всех точек в , расстояние от которых до не превышает их расстояние до других сайтов , где – любой индекс, отличный от . Другими словами, если обозначает расстояние между точкой и подмножеством , то диаграмма Вороного – это просто кортеж ячеек. В принципе, некоторые из сайтов могут пересекаться и даже совпадать (пример применения описан ниже для сайтов, представляющих магазины), но обычно предполагается, что они не пересекаются. Кроме того, в определении допускается бесконечное число сайтов (это имеет применение в геометрии чисел и кристаллографии), но во многих случаях рассматривается лишь конечное число сайтов. В частности, если пространство является конечномерным евклидовым пространством, каждый сайт является точкой, существует конечное число точек и все они различны, то воронковские ячейки являются выпуклыми многогранниками и могут быть представлены комбинаторно, используя их вершины, ребра, двумерные грани и т. д. Иногда индуцированная комбинаторная структура называется диаграммой Вороного. Однако, в общем случае, воронковские ячейки могут быть невыпуклыми или даже несвязными. В обычном евклидовом пространстве мы можем переформулировать формальное определение в обычных терминах. Каждому воронковскому полигону соответствует генерирующая точка . Пусть – множество всех точек в евклидовом пространстве. Пусть – точка, генерирующая свою воронковскую область , – точка, генерирующая , и – точка, генерирующая , и так далее. Тогда, как выразились Тран и др., "все точки внутри воронковского полигона ближе к генерирующей точке этого полигона, чем любая другая генерирующая точка на диаграмме Вороного в евклидовой плоскости".

Свойства

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

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

Неформальное использование диаграмм Вороного можно проследить до Декарта в 1644 году. Питер Густав Лежен Дирихле использовал двумерные и трехмерные диаграммы Вороного в своем исследовании квадратичных форм в 1850 году. Британский врач Джон Сноу использовал диаграмму, подобную диаграмме Вороного, в 1854 году, чтобы проиллюстрировать, как большинство людей, умерших во время вспышки холеры на Брод-стрит, жили ближе к зараженному насосу на Брод-стрит, чем к любому другому водяному насосу. Диаграммы Вороного названы в честь Георгия Феодосиевича Вороного, который определил и изучил общий n-мерный случай в 1908 году. Диаграммы Вороного, используемые в геофизике и метеорологии для анализа пространственно распределенных данных, называются полигонами Тиссена в честь американского метеоролога Альфреда Х. Тиссена, который использовал их для оценки количества осадков на основе рассеянных измерений в 1911 году. Другие эквивалентные названия для этого понятия (или его особых важных случаев): полиэдры Вороного, полигоны Вороного, области влияния, разложение Вороного, тесселяции Вороного, тесселяции Дирихле.

Примеры

Вороновские разбиения на ячейки регулярных решеток точек в двух или трех измерениях порождают множество известных разбиений. Двумерная решетка дает нерегулярную сотовую структуру, состоящую из равных шестиугольников с точечной симметрией; в случае регулярной треугольной решетки она является регулярной; в случае прямоугольной решетки шестиугольники вырождаются в прямоугольники, расположенные рядами и столбцами; квадратная решетка дает регулярное разбиение на квадраты; следует отметить, что прямоугольники и квадраты также могут быть сгенерированы другими решетками (например, решетка, определяемая векторами (1,0) и (1/2,1/2) дает квадраты). Простая кубическая решетка дает кубическую сотовую структуру. Гексагональная плотноупакованная решетка дает разбиение пространства на трапециевидные ромбододекаэдры. Кубическая решетка с центрированием на гранях дает разбиение пространства на ромбододекаэдры. Кубическая решетка с центрированием в теле дает разбиение пространства на усеченные октаэдры. Параллельные плоскости с регулярными треугольными решетками, центры которых выровнены друг относительно друга, дают шестиугольную призматическую сотовую структуру. Определенные тетрагональные решетки с центрированием в теле дают разбиение пространства на ромбогексагональные додекаэдры. Определенные тетрагональные решетки с центрированием в теле дают разбиение пространства на ромбогексагональные додекаэдры. Для множества точек (x, y), где x принадлежит дискретному множеству X, а y принадлежит дискретному множеству Y, мы получаем прямоугольные плитки, в которых точки не обязательно находятся в их центрах.

Диаграммы Воронои высшего порядка

Хотя нормальная ячейка Вороного определяется как множество точек, ближайших к одной точке в S, ячейка Вороного n-го порядка определяется как множество точек, для которых заданный набор из n точек в S является n ближайшими соседями. Диаграммы Вороного более высокого порядка также разбивают пространство на области. Диаграммы Вороного более высокого порядка могут быть сгенерированы рекурсивно. Для генерации диаграммы Вороного n-го порядка из множества S начните с диаграммы (n-1)-го порядка и замените каждую ячейку, сгенерированную множеством X = {x1, x2, ..., xn−1}, диаграммой Вороного, сгенерированной на множестве S - X.

Диаграмма Вороноя с самой отдаленной точкой

Для множества из n точек диаграмма Вороного (n − 1)-го порядка называется диаграммой Вороного наиболее удалённой точки. Для заданного набора точек S = {p1, p2, …, pn} диаграмма Вороного наиболее удалённой точки разбивает плоскость на ячейки, в каждой из которых одна и та же точка из P является наиболее удалённой точкой. Точка P имеет ячейку в диаграмме Вороного наиболее удалённой точки тогда и только тогда, когда она является вершиной выпуклой оболочки P. Пусть H = {h1, h2, …, hk} является выпуклой оболочкой P; тогда диаграмма Вороного наиболее удалённой точки представляет собой разбиение плоскости на k ячеек, по одной для каждой точки в H, со свойством, что точка q принадлежит ячейке, соответствующей точке hi, тогда и только тогда, когда d(q, hi) > d(q, pj) для каждой точки pj ∈ S, где hi ≠ pj, при этом d(p, q) – евклидово расстояние между двумя точками p и q. Границы ячеек в диаграмме Вороного наиболее удалённой точки имеют структуру топологического дерева с бесконечными лучами в качестве листьев. Любое конечное дерево изоморфно дереву, построенному таким образом из диаграммы Вороного наиболее удалённой точки.

Обобщения и вариации

Как следует из определения, ячейки Вороного могут быть определены для метрик, отличных от евклидовой, таких как расстояние Махаланобиса или расстояние Манхэттена. Однако в этих случаях границы ячеек Вороного могут быть более сложными, чем в евклидовом случае, поскольку геометрическое место точек, равноудалённых от двух точек, может не являться подпространством коразмерности 1, даже в двумерном случае. Взвешенная диаграмма Вороного – это диаграмма, в которой функция, определяющая ячейку Вороного на основе пары точек, представляет собой функцию расстояния, модифицированную мультипликативными или аддитивными весами, присвоенными генераторным точкам. В отличие от ячеек Вороного, определенных с использованием расстояния, являющегося метрикой, в этом случае некоторые ячейки Вороного могут быть пустыми. Диаграмма мощностей – это тип диаграммы Вороного, определяемый на основе набора окружностей с использованием расстояния мощностей; её также можно рассматривать как взвешенную диаграмму Вороного, в которой вес, определяемый радиусом каждой окружности, добавляется к квадрату евклидова расстояния от центра окружности. Диаграмма Вороного для точек в -мерном пространстве может иметь вершин, что требует аналогичной границы для объема памяти, необходимого для хранения её явного описания. Поэтому диаграммы Вороного часто не применимы для умеренных или высоких размерностей. Более эффективной с точки зрения использования памяти альтернативой является использование приближенных диаграмм Вороного. Диаграммы Вороного также связаны с другими геометрическими структурами, такими как медиальная ось (которая нашла применение в сегментации изображений, оптическом распознавании символов и других вычислительных задачах), прямой скелет и диаграммы зон.

Метеорология/гидрология

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

Гуманитарные и социальные науки

В классической археологии, особенно в искусствоведении, симметрия голов статуй анализируется для определения типа статуи, к которой могла принадлежать отделённая голова. Примером этого является идентификация головы Сабуроффа, в которой использовались воронóйские ячейки и высокоразрешальная полигональная сетка.

Природные науки

В биологии диаграммы Вороного используются для моделирования ряда различных биологических структур, включая клетки и микроархитектуру костей. Фактически, тесселяции Вороного служат геометрическим инструментом для понимания физических ограничений, определяющих организацию биологических тканей. В гидрологии диаграммы Вороного используются для расчета количества осадков на территории, основываясь на серии точечных измерений. В этом случае они обычно называются полигонами Тейсена. В экологии диаграммы Вороного используются для изучения закономерностей роста лесов и лесных крон, а также могут быть полезны при разработке прогностических моделей лесных пожаров. В этологии диаграммы Вороного используются для моделирования зон опасности в теории эгоистичного стада. В вычислительной химии сайты связывания лигандов преобразуются в диаграммы Вороного для задач машинного обучения (например, для классификации связывающих карманов в белках). В других приложениях воронковские ячейки, определяемые положениями ядер в молекуле, используются для вычисления атомных зарядов. Это выполняется с использованием метода плотности деформации Вороного. В астрофизике диаграммы Вороного используются для создания адаптивных зон сглаживания на изображениях, суммируя потоки сигнала в каждой из них. Основная цель этих процедур – поддержание относительно постоянного отношения сигнал/шум на всех изображениях. В вычислительной гидродинамике тесселяция Вороного набора точек может использоваться для определения вычислительных областей, применяемых в методах конечных объемов, например, как в космологическом коде с движущейся сеткой AREPO. В вычислительной физике диаграммы Вороного используются для расчета профилей объекта методами теневой графики и протонной рентгенографии в физике высоких плотностей энергии.

Здоровье

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

Инженерная

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

Математика

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

Информатика

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

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

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

Пекарня

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

Алгоритмы

Известно несколько эффективных алгоритмов построения диаграмм Вороного, либо напрямую (как саму диаграмму), либо косвенно, начиная с триангуляции Делоне и затем получая её двойственную форму. К прямым алгоритмам относится алгоритм Фортуна – алгоритм со сложностью O(n log(n)) для генерации диаграммы Вороного из набора точек на плоскости. Алгоритм Бойера — Уотсона, алгоритм со сложностью от O(n log(n)) до O(n²), для генерации триангуляции Делоне в любом числе измерений, может быть использован в косвенном алгоритме для диаграммы Вороного. Алгоритм Jump Flooding позволяет генерировать приближённые диаграммы Вороного за постоянное время и хорошо подходит для использования на стандартном графическом оборудовании. Алгоритм Ллойда и его обобщение посредством алгоритма Линде — Бузо — Грея (также известного как k-средних) используют построение диаграмм Вороного в качестве подпрограммы. Эти методы попеременно выполняют этапы построения диаграммы Вороного для набора начальных точек и этапы перемещения этих точек в новые положения, более центральные в их ячейках. Эти методы могут применяться в пространствах произвольной размерности для итеративного схождения к специализированной форме диаграммы Вороного, называемой центроидальной тесселяцией Вороного, где точки (сайты) перемещены в положения, являющиеся также геометрическими центрами их ячеек.

Вороной в 3D

Вороные диаграммы также могут быть сгенерированы в 3D.