Попередня Змiст Наступна

5.4.Діаграма Вороного. Властивості.

Многокутники Вороного (МВ) вперше глибоко були вивчені українським математиком Г. Вороним (1868-1908), який використовував їх у роботі з квадратичних форм. Інколи їх також називають многокутниками (комірками) Діріхле, Тіссена, Вігнера-Зейтца, "многокутниками близькості". У ряді застосувань кінцевою метою є саме побудова ДВ. У археології МВ використовуються для нанесення на карту ареалу застосування знарядь праці у стародавніх культурах і для вивчення впливу конкуренції центрів торгівлі. У екології можливості організму на виживання залежать від числа сусідів, із якими він повинен боротися за їжу та світло. У біології використання ДВ, яка відображає картину розселення тварин і розподілу життєво важливих ресурсів, допомагає досліджувати та вивчати ефект перенаселення. Вивчення та дослідження клітинних структур живої матерії.
У фізиці сумісний вплив електричних і близькодіючих сил, для вивчення яких будуються складні ДВ, допомагає визначити структуру молекул.
Задача Б.7 ( ОБЛАСТІ БЛИЗЬКОСТІ ). На площині задана множина S, яка містить N точок. Необхідно для кожної точки pi множини S визначити локус точок (x, y) на площині, для яких відстань до pi менша, ніж до будь - якої іншої точки множини S.
Якщо є дві точки pi та pj, то множина точок, більш близьких до pi, ніж до pj, є півплощина, що визначається прямою, яка перпендикулярна до відрізка pipj та ділить його навпіл. Позначимо цю півплощину через H(pi, pj). Множину точок, більш близьких до pi, ніж до іншої довільної точки, будемо позначати через Vі. Вона одержується в результаті перетину N - 1 півплощин. Ця множина є опуклим многокутником, який має не більш ніж N - 1 сторін.
Означення 5.5 Область Vі називається многокутником Вороного, яка відповідає точці pi. Отримані таким чином N областей утворюють розбиття площини, яке називається діаграмою Вороного. Діаграму Вороного множини точок S будемо позначати через Vor(S).
Мал. 5.12.

Кожна з N вихідних точок множини належить лише одному многокутнику Вороного. Тому якщо (x, y) Vі, то pi є найближчим сусідом точки (x, y).
Властивості діаграми Вороного
  1. Припущення. Жодні чотири точки вихідної множини S не лежать на одному колі.
  2. Теорема 5.5 Кожна вершина діаграми Вороного є точкою перетину трьох ребер діаграми.
    Мал. 5.13. Вершина діаграми Вороного з інциндентними їй вершинами.
    Доведення. Нехай v є точкою перетину ребер e1, e2, ..., ek. Ребро ei є спільним для многокутників V(i - 1) та V(i), i = 2, ..., k, а ребро e1 є спільним для V(k) та V(1). Оскільки v належить ребру ei, то вона однаково віддалена від точок pi-1 та pi. Таким чином v рівновіддалена від точок p1, p2, ..., pk. Це означає, що точки p1, p2, ..., pk лежать на одному колі, що суперечить припущенню.
  3. Вершини діаграми Вороного є центрами кіл, кожне з яких визначається трьома точками вихідної множини, а сама діаграма Вороного є регулярною (всі вершини мають однаковий ступінь) зі ступенем вершин, що дорівнює трьом. Позначимо через C(v) коло, що відповідає вершині v.
Теорема 5.6 Для будь-якої вершини v діаграми Вороного множини S коло C(v) не містить жодних інших вершин множини S.
Мал. 5.14. Коло С(v) не містить жодної точки множини S.
Доведення. Нехай p1, p2, p3 - три точки множини S, які визначають коло C(v). Якщо коло містить ще деяку точку p4 множини S, то вершина v знаходиться ближче до p4, ніж до інших точок. Тоді вершина v має знаходитися у V(4), що суперечить тому, що v належить одночасно V(1), V(2) та V(3).
Теорема 5.7 Кожний найближчий сусід точки pi множини S визначає ребро у многокутнику Вороного Vi.
Мал. 5.15. Кожен найближчий сусід точки рі визначає ребро многокутника Vі.
Доведення. Нехай pi є найближчим сусідом pj, а v - середина відрізка, що їх з'єднує. Припустимо, що v не лежить на границі Vi. Тоді відрізок перетинає деяке ребро многокутника Vi (наприклад, рівновіддалене від pi та pk) в деякій точці u. Тоді |piu| < |piv| і тому |pipk| 2 |piu| < 2 |piv| = |pipj|, звідки випливає, що pk ближче до pi ніж pj, що суперечить умові теореми.
Теорема 5.8 Многокутник Vi є необмеженим тоді і тільки тоді, коли точка pi лежить на границі опуклої оболонки множини S.
Мал. 5.16. Прямолінійний граф, двоїстий діаграмі Воронного.
Теорема 5.9 Граф, двоїстий діаграмі Вороного, є тріангуляцією множини S.
Теорема 5.10 Діаграма Вороного множини з N точок має не більш 2N - 5 вершин та 3N - 6 ребер.
Доведення. Кожному ребру графа, двоїстого діаграмі Вороного, відповідає єдине ребро діаграми. Двоїстий граф є тріангуляцією, а отже є планарним графом з N вершинами. За формулою Ейлера він має не більше ніж 3N - 6 ребер та 2N - 4 граней. Лише обмежені грані (їх не більше ніж 2N - 5) відповідають вершинам діаграми Вороного при відображенні двоїстості.

Попередня Змiст Наступна