Презентація на тему:
Вороний Георгій Феодосійович

Вороний Георгій Феодосійович (28 квітня, 1868 — 20 листопада, 1908) - відомий Російський математик українського походження. Народився в с. Журавка, нині Варвинського району, Чернігівської області На честь Вороного названі діаграми Вороного, що застосовуються у інформатиці. Навчався у Санкт-Петербурзький університеті у Андрія Маркова. Працював у Варшавському університеті, де вивчав ланцюгові дроби. У Варшаві у Вороного навчався Вацлав Серпінський. Справжнє значення започаткованих ним наприкінці минулого - початку нинішнього століття нових напрямків у галузі теорія чисел розкривається лише в наш час. Праці Георгія Вороного набули особливо великого значення за останні двадцять років. Це пов'язано із розвитком комп'ютерної графіки, молекулярної біології, радіаційної фізики, космології, творенням штучного інтелекту За своє коротке (40 років) життя Г.Вороний написав усього 12 наукових робіт, але 8 з них успішно використовуються саме тепер. Це - унікальне явище, зокрема в математиці, де будь-жі відкриття вже через 2-3 роки вважаються застарілими. Вихід

Діаграма Вороного Задача. Області близькості. На площині задана множина S, яка містить N точок. Необхідно для кожної точки pi множини S визначити локус точок (x, y) на площині, для яких відстань до pi менша, ніж до будь - якої іншої точки множини S. Якщо є дві точки pi та pj, то множина точок, більш близьких до pi ніж до pj, є півплощина, що визначається прямою, яка перпендикулярна до відрізка pipj та ділить його навпіл. Позначимо цю півплощину через H(pi, pj). Множину точок, більш близьких до pi ніж до довільної іншої точки, будемо позначати через V(i). Вона отримується в результаті перетину N - 1 півплощин. Ця множина є опуклим многокутником, який має не більш ніж N - 1 сторон. V(i) = H(pi, pj) Означення. Область V(i) називається многокутником Вороного, яка відповідає точці pi. Отримані таким чином N областей утворюють розбиття площини, яке називається діаграмою Вороного. Діаграму Вороного множини точок S будемо позначати через Vor (S). Кожна з N вихідних точок множини належить лише одному многокутнику Вороного. Тому якщо (x, y) Î V(i), то pi є найближчим сусідом точки (x, y). Твердження. Жодні чотири точки вихідної множини S не лежать на одному колі. Теорема. Кожна вершина діаграми Вороного є точкою перетину трьох ребер діаграми. Доведення. Нехай v є точкою перетину ребер e1, e2, ..., ek. Ребро ei є спільним для многокутників V(i - 1) та V(i), i = 2, ..., k, а ребро є спільним для V(k) та V(1). Оскільки v належить ребру ei, то вона однаково віддалена від точок pi-1 та pi. Таким чином v рівновіддалена від точок p1, p2, ..., pk. Це означає, що точки p1, p2, ..., pk лежать на одному колі, що суперечить припущенню. Вершини діаграми Вороного є центрами кіл, кожне з яких визначається трьома точками вихідної множини, а сама діаграма Вороного є регулярною (всі вершини мають однаковий ступінь) зі ступенем вершин, рівним трьом. Позначимо через C(v) коло, що відповідає вершині v. Вихід

Теорема. Для кожної вершини v діаграми Вороного множини S коло C(v) не містить жодних інших вершин множини S Доведення. Нехай p1, p2, p3 – три точки множини S, які визначають коло C(v). Якщо коло містить ще деяку точку p4 множини S, то вершина v знаходиться ближче до p4 ніж до інших точок. Тоді вершина v повинна знаходитися у V(4), що суперечить тому що v належить одночасно V(1), V(2) та V(3). Теорема. Кожний найближчий сусід точки pi множини S визначає ребро у многокутнику Вороного V(i). Нехай pi є найближчим сусідом pj, а v – середина з’єднуючого їх відрізка. Припустимо, що v не лежить на границі V(i). Тоді відрізок перетинає деяке ребро многокутника V(i) (наприклад рівновіддалене від pi та pk) в деякій точці u. Тоді |piu| < |piv| і тому |pipk| £ 2 |piu| < 2 |piv| = |pipj|, звідки випливає що pk ближче до pi ніж pj, що суперечить умові теореми. Вихід

Теорема. Многокутник V(i) є необмеженим тоді і тільки тоді, коли точка pi лежить на границі опуклої оболонки множини S. Теорема. Граф, двоїстий діаграмі Вороного, є триангуляцією множини S. Теорема. Діаграма Вороного множини з N точок має не більш 2N - 5 вершин та 3N - 6 ребер. Доведення. Кожному ребру графа, двоїстого діаграмі Вороного, відповідає єдине ребро діаграми. Двоїстий граф є триангуляцією, а отже є планарним з N вершинами. За формулою Ейлера він має не більш ніж 3N - 6 ребер та 2N - 4 граней. Лише обмежені грані (їх не більш ніж 2N - 5) відповідають вершинам діаграми Вороного при відображенні двоїстості. Вихід

Побудова діаграми Вороного Означення. Нехай для заданого розбиття {S1, S2}множини S s(S1, S2) означає множину ребер діаграми Вороного, спільних для пар многокутників V(i) та V(j) діаграми Vor(S), де pi Î S1 та pj Î S2. Сукупність ребер має наступні властивості: 1. s(S1, S2) складається із циклів та ланцюгів, що не мають спільних ребер. Якщо деякий ланцюг містить єдине ребро, то це ребро є прямою лінією; інакше два крайні ребра ланцюга є промінями. 2. Якщо множини S1 та S2 є лінійно роздільними, то s(S1, S2) складається з єдиного монотонного ланцюга. Діаграма Вороного Крок 1. Розділити множину S на дві приблизно рівні підмножини S1 та S2, використавши для цього медіану по x координаті. Крок 2. Рекурсивно побудувати Vor(S1) та Vor(S2). Крок 3. Побудувати ламану s, що розділяє S1 та S2. Крок 4. Видалити всі ребра діаграми Vor(S2), розташовані зліва від s та всі ребра Vor(S1), розташовані справа від s. Отримаємо Vor(S) – діаграму Вороного для всієї множини. Побудова розділяючого ланцюга Кожний промінь ланцюга s перпендикулярний опорному відрізку до CH(S1) та CH(S2) і ділить його навпіл. Оскільки S1 та S2 за припущенням лінійно роздільні, то існує рівно два опорних відрізка до CH(S1) та CH(S2). проміні розділяючого ланцюга опорні відрізки CH(S1) CH(S2) Вихід

Приклад побудови діаграми Вороного Множина точок S ліва частина права частина верхня частина верхня частина нижня частина нижня частина ліва частина права частина ЧЕРВОНИЙ КОЛІР: діаграма Вороного лівої верхньої частини СИНІЙ КОЛІР: діаграма Вороного лівої нижньої частини Вихід

ліва верхня множина точок опорні прямі ліва нижня множина точок розділяючий ланцюг діаграма Вороного лівої частини ЧЕРВОНИЙ КОЛІР: діаграма Вороного правої верхньої частини СИНІЙ КОЛІР: діаграма Вороного правої нижньої частини розділяючий ланцюг Діаграма Вороного множини S Вихід