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

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

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

У найпростішому випадку, ми маємо множину точок площини 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, тоді легко накреслити зображення теселяції Вороного, у цьому випадку вона часто зветься діаграмою Вороного.

Властивості[ред.ред. код]

У кіно[ред.ред. код]

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

Ілюстрація[ред.ред. код]

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

Досі мало місце припущення, що відстань між точками міста вимірюється із використанням знайомої відстані Евкліда: \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}

Однак, якщо ми припустимо, що споживачі лише їздять у магазин і дороги паралельні до осей  x і  y , як у відстані таксиста, тоді реалістичнішою функцією буде 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. (нім.)