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

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

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

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

редактиране

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

  1. Сред множеството О има единствена Оi, за която ОiХ е най-малко
  2. Сред множеството О има две точки Oi и Oj, за които ОiХ=ОjХ е най-малко
  3. Сред множеството О има три или повече Oi1, Оi2, ... Оin, за които разстоянието до Х е най-късо

В първия случай Х принадлежи на многоълника Pi. Във втория случай Х е на ръба между многоълниците Рi и Рj. В третия случай това е точката, обща за многоълниците Рi1, Рi2, ... Рin.

Свойства

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

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

редактиране

Източници

редактиране
  • Aurenhammer, Franz, Klein, Rolf, Lee, Der-Tsai. Voronoi Diagrams and Delaunay Triangulations. World Scientific, 2013. ISBN 978-9814447638.