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

В математиката, диаграма на Вороной е вид пълно разделение на метрично пространство, определено от разстояния до дадено множество точки. Диаграмата носи името на руския математик Григорий Вороной и е още известна като декомпозиция на Вороной и мозайка на Вороной.

Пример за варианта на диаграмата в двуизмерно пространство с произволни точки (многоъгълниците са оцветени за удобство)

В най-простия си и най-широко използван вариант, в равнина със зададени точки O_{i, i=(0..n)}, диаграмата на Вороной представлява множеството многоъгълници P_{i, i=(0..n)}, такова че P_i, съдържа O_i, и най-близката до всяка точка в рамките на P_i е именно O_i.

Формална дефиниция

Нека O_{i, i=(0..n)} е множество от точки в пространството. За всяка точка X от пространството имаме една от трите възможности.

1. Сред множеството О има единствена О_i, за която О_iХ е най-малко
2. Сред множеството О има две точки O_i и O_j, за които О_iХ=О_jХ е най-малко
3. Сред множеството О има три или повече O_i1, О_i2, ... О_in, за които разстоянието до Х е най-късо

В първия случай Х принадлежи на многоълника P_i. Във втория случай Х е на ръба между многоълниците Р_i и Р_j. В третия случай това е точката, обща за многоълниците Р_i1, Р_i2, ... Р_in.

Свойства

• Всяка точка от О споделя ръб с най-близката до нея
• Ръбът между две точки от О, представлява симетрала на отсечката, образувана от тях
• Две точки от O са съседни върху изпъкналото обкръжение на О тогава и само тогава, когато споделят безкраен ръб
• Двойственият на графа, образуван от върховете и ръбовете на многоълниците, представлява триангулация на Делоне на множеството О

Външни препратки

https://www.mathworks.com/help/matlab/ref/voronoi.html Функция на Matlab, която изчертава диаграма на Вороной по зададени вектори x и y с координати на точки.

Източници

• Aurenhammer, Franz, Klein, Rolf, Lee, Der-Tsai. Voronoi Diagrams and Delaunay Triangulations. World Scientific, 2013. ISBN 978-9814447638.