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

от Уикипедия, свободната енциклопедия
Направо към: навигация, търсене

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

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

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

Формална дефиниция[редактиране | edit source]

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

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

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

Свойства[редактиране | edit source]

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