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

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

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

Властивості

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

У кіно

Застосування діаграми Вороного можна побачити у 10-й серії 2-го сезону американського серіалу "4исла" (Numb3rs), коли проф. Чарлі під час розслідування одного з убивств, пов'язаного з археологічною знахідкою, вичисляє можливий район наступних археологічних розкопок, які має здійснити вбивця. Як приклад, застосування діаграми Вороного наводить розташування мережі закусочних.

Посилання

• Gustav Lejeune Dirichlet (1850). Über die Reduktion der positiven quadratischen Formen mit drei unbestimmten ganzen Zahlen. Journal für die Reine und Angewandte Mathematik, 40:209-227. (нім.)