Взвешенная диаграмма Вороного
В математике взвешенная диаграмма Вороного в n измерениях является обобщением диаграммы Вороного . Ячейки Вороного во взвешенной диаграмме Вороного определяются с точки зрения функции расстояния. Функция расстояния может указывать обычное евклидово расстояние или может быть какой-либо другой специальной функцией расстояния. Во взвешенных диаграммах Вороного каждый сайт имеет вес, который влияет на вычисление расстояния. Идея состоит в том, что больший вес указывает на более важные сайты, и такие сайты получат более крупные ячейки Вороного.
В мультипликативно взвешенной диаграмме Вороного расстояние между точкой и сайтом делится на (положительный) вес сайта. [1] В плоскости под обычным евклидовым расстоянием мультипликативно взвешенная диаграмма Вороного также называется круговой мозаикой Дирихле. [2] [3] а его края представляют собой дуги окружностей и отрезки прямых. Ячейка Вороного может быть невыпуклой, несвязной и иметь дырки. Эта диаграмма возникает, например, как модель роста кристаллов , где кристаллы из разных точек могут расти с разной скоростью. Поскольку кристаллы могут расти только в пустом пространстве и являются непрерывными объектами, естественным вариантом является кристаллическая диаграмма Вороного , в которой ячейки определены несколько иначе.
В аддитивно взвешенной диаграмме Вороного веса вычитаются из расстояний. В плоскости под обычным евклидовым расстоянием эта диаграмма также известна как гиперболическая мозаика Дирихле , а ее края представляют собой дуги гипербол и отрезки прямых. [1]
Силовая диаграмма определяется, когда веса вычитаются из квадрата евклидова расстояния. Его также можно определить с помощью дистанции власти , определенной из набора кругов. [4]
Ссылки
[ редактировать ]- ^ Jump up to: а б «Словарь расстояний», Елены Деза и Мишеля Деза, стр. 255, 256.
- ^ Питер Ф. Эш и Итан Д. Болкер, [Обобщенные мозаики Дирихле https://doi.org/10.1007%2FBF00164401 ], Geometriae Dedicata , Том 20, Номер 2, 209-243 два : 10.1007/BF00164401
- ^ Примечание: « Мозаика Дирихле » является синонимом «диаграммы Вороного».
- ^ Эдельсбруннер, Герберт (1987), «13.6 Степенные диаграммы», Алгоритмы в комбинаторной геометрии , Монографии EATCS по теоретической информатике, том. 10, Springer-Verlag, стр. 327–328 .