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

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

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

В най-простия си и най-широко използван вариант, в равнина със зададени точки 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 са съседни върху изпъкналото обкръжение на О тогава и само тогава, когато споделят безкраен ръб
• Двойственият на графа, образуван от върховете и ръбовете на политопите, представлява триангулация на Делоне на множеството О