Діаграма Вороного

Діаграма Вороного для випадкової множини точок на площині (всі точки лежать всередині зображення).

Діаграма Вороного - це особливий вид розбиття метричного простору що визначається відстанями до заданої дискретної множини ізольованих точок цього простору. Вона названа на честь Георгія Вороного. Інші назви - теселяція Вороного, декомпозиція Вороного, чи Тесселяція Діріхле (на честь Лежьона Діріхле).

Властивості

• Дуальний граф для діаграми Вороного відповідає тріангуляції Делоне для такої ж множини точок S.
• Найближча пара точок відповідає двом суміжним cells в діаграмі Вороного.
• Дві точки суміжні на опуклій оболонці тоді і тільки тоді коли їхні Voronoi cells мають спільну грань нескінченної довжини.