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

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

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

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

Означення

Нехай S буде множиною вершин в евклідовому просторі з усіма граничними точками в S. Для майже всіх точок x в Евклідовому просторі, існує одна точка в S найближча до x. Слово майже використане для позначення винятків, де точка x може буде рівновіддалена від двох або більшої кількості точок з S.

Якщо S містить лише дві точки, a і b, тоді множина всіх точок рівновіддалених від них це гіперплощина — афінний підпростір корозмірності 1. Ця гіперплощина є границею між множинами всіх точок ближчих до a ніж до b і до b ніж до a. Це буде перпендикулярний (бісектор) лінії від a до b.

Множина всіх точок ближчих до точки c з множини S ніж до будь-якої іншої з S є внутрішністю (іноді необмеженою) опуклого політопа відомого як домен Діріхле або комірка Вороного для c. Множина таких політопів розбиває увесь простір і є теселяцією Вороного відповідною множині S. Якщо розмірність простору 2, тоді легко накреслити зображення теселяції Вороного, у цьому випадку вона часто зветься діаграмою Вороного.

Властивості

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

Оцінка кількості ребер і вершин

Для ${\displaystyle n\geq 3}$ кількість вершин у діаграмі Вороного з ${\displaystyle n}$ точок на площині становить не більше ніж ${\displaystyle 2n-5}$ і кількість ребер не більше ніж ${\displaystyle 3n-6.}$

Доведення: Для доведення теореми ми хотіли б використати (формулу Ейлера). Але наш граф має ребра, які є променями. Для виправлення цього ми додамо ще одну вершину ${\displaystyle v_{\infty }}$ і всі такі ребра спрямуємо до неї. Тепер, якщо початкова діаграма Вороного мала ${\displaystyle V}$ вершин і ${\displaystyle E}$ ребер, то формула Ейлера набуває вигляду:

${\displaystyle (V+1)-E+n=2,}$

кількість граней і є кількістю точок — ${\displaystyle n.}$

Тепер нам потрібно оцінити кількості ребер і вершин. Ми знаємо, що у доповненому графі кожне ребро має саме дві вершини. Отже, якщо ми просумуємо степені вершин, то отримуємо число ребер помножене на два. Оскільки у діаграмі Вороного кожна вершина має щонайменше 3 інцидентних ребра, то маємо:

${\displaystyle 2E\geq 3(V+1).}$

Для отримання заявлених кількостей підставляємо отриману нерівність у рівняння Ейлера.

Алгоритми побудови

Побудова діаграми Вороного алгоритмом Форчуна.

Алгоритм Форчуна

Докладніше: Алгоритм Форчуна

Алгоритм заснований на застосуванні замітання прямою. Замітальна пряма — це допоміжний об'єкт, що є вертикальною прямою лінією. На кожному кроці алгоритму діаграма Вороного побудована для множини, що складається з замітальної прямої та точок ліворуч від неї. При цьому межа між областю Вороного прямою та областями точок складається з відрізків парабол (оскільки геометричне місце точок, рівновіддалених від заданої точки та прямої — це парабола). Пряма рухається зліва направо. Щоразу, коли вона проходить через чергову точку, ця точка додається до вже побудованої ділянки діаграми. Додавання точки до діаграми при використанні двійкового дерева пошуку має складність ${\displaystyle O(\log n)}$, всього точок ${\displaystyle n}$, а сортування точок по ${\displaystyle x}$-координаті може бути виконана за ${\displaystyle O(n\log n)}$, тому обчислювальна складність алгоритму Форчуна дорівнює ${\displaystyle O(n\log n)}$.

У кіно

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

Ілюстрація

Як простий приклад, розглянемо групу крамниць в місті на площині. Припустимо ми хочемо оцінити кількість споживачів певної крамниці. За умови рівності цін, товарів, якості обслуговування та інших параметрів, розумно вважати, що споживачі обирають найближчу крамницю, тобто, важить лише відстань. В цьому випадку комірку Вороного ${\displaystyle \scriptstyle R_{k}}$ для певної крамниці ${\displaystyle \scriptstyle P_{k}}$ можна використати як грубу оцінку кількості потенційних клієнтів, що відвідують цю крамницю (яка відтворена як точка на мапі міста).

Досі мало місце припущення, що відстань між точками міста вимірюється із використанням знайомої відстані Евкліда: ${\displaystyle \ell _{2}=d\left[\left(a_{1},a_{2}\right),\left(b_{1},b_{2}\right)\right]={\sqrt {\left(a_{1}-b_{1}\right)^{2}+\left(a_{2}-b_{2}\right)^{2}}}}$

Однак, якщо ми припустимо, що споживачі лише їздять у магазин на авто і дороги паралельні до осей ${\displaystyle x}$ та ${\displaystyle y}$, тоді має сенс використовувати відстань таксиста, яка обчислюється наступним чином ${\displaystyle d\left[\left(a_{1},a_{2}\right),\left(b_{1},b_{2}\right)\right]=\left|a_{1}-b_{1}\right|+\left|a_{2}-b_{2}\right|}$.

діаграма Вороного 20 точок з двома різними метриками

Евклідова відстань

Мангеттенська відстань

Див. також

• Найбільша порожня сфера
• Список об'єктів, названих на честь Георгія Вороного

Посилання

• 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. (нім.)