Озвучена стаття Математика — 19 серпня, 2019

Всесвіт ученого Вороного

ТЕКСТ:

ІЛЮСТРАЦІЇ: Куншт

У ХІХ столітті український математик Георгій Вороний знайде розв’язок задачі про пошук найближчого сусіда або області близькості. Цей метод отримав назву діаграма Вороного й отримав широке практичне застосування: від садівництва та розбудови інфраструктури міст до астрономії. Що це таке і як його застосовують у різних галузях – читайте у нашій статті.

Напевно, кожен ставив собі в шкільні часи запитання: «Навіщо мені вчити геометрію, поясніть, де її використовують на практиці?». Наведемо приклад, як широко може застосовуватись проста задача з геометрії про пошук найближчого сусіда, яку запропонував Георгій Вороний, український вчений, про роботи якого так багато відомо в світі і так мало в Україні.

31 серпня 1854 року в Лондоні почалась епідемія холери, яка за декілька місяців забрала життя 600 людей. Щоб знайти джерело хвороби, сорокарічний лікар Джон Сноу відмітив на карті місця розташування колонок, де місцеві мешканці набирали воду. Джон також позначив будинки й кількість померлих в них. Так він пов’язав місця поширення захворювання з потенційними його джерелами. Дослідження показало, що найбільше число померлих припало на околиці водозабірної колонки на Брод-стріт. Лікар з’ясував, що компанія, яка постачала воду мешканцям будинків, де частіше траплялися випадки захворювання на холеру, брала її в забруднених частинах Темзи. 

Коли Сноу зіставив місця захворювань з потенційними його джерелами, він отримав метод, який через півстоліття математично обґрунтує Георгій Вороний. Цей метод був названий на його честь і набув великої популярності.  Георгій Вороний – видатний математик, якого в Україні називають українським вченим, в Росії – російським, а в Польщі – польським з українським корінням, оскільки роки його життя (1868–1908) припадають на час, коли частина України та Польщі входили до складу Російської імперії. 

Народився він у селі Журавка Чернігівської області, закінчив Прилуцьку чоловічу гімназію. Завдяки чудовим математичним здібностям Георгій Вороний зміг поступити в один із найкращих університетів у Російській імперії – Санкт-Петербурзький університет. Після захисту дисертації він хотів викладати в Київському університеті, але через проукраїнські погляди його відправили подалі від України до Варшавського університету, де він, зрештою, захистив докторську дисертацію.

Діаграма Вороного або мозаїка Вороного, теселяція Вороного, декомпозиція Вороного – це геометричний спосіб розв’язання задачі про пошук найближчого сусіда або області близькості. Візьмемо розкидані на площині точки (ядра, у випадку Сноу – це джерела, звідкіля лондонці набирали воду), між двома точками (ядрами) проводимо пряму, знаходимо її середину і будуємо до неї перпендикуляр. Те саме повторюємо з іншими точками, а потім з’єднуємо перпендикуляри до точки їх перетину (як це показано на мал. 1.). У результаті утворюються комірки для кожного ядра, кожна точка площини комірки ближча до свого ядра, ніж до будь-якого іншого. Джон Сноу позначив біля кожного джерела (ядра комірки Вороного) будинки, у яких померли лондонці, і так визначив джерела зараження.

Коли виникає питання щодо розміщення нової школи, лікарні чи поштового відділення, на допомогу приходить саме метод мозаїки Вороного, який допоможе ефективно вирішити це завдання. Наприклад, у австралійському штаті Вікторія урядові школи зазвичай приймають учнів у найближчу школу залежно від їх місця проживання. Існує інтернет-додаток, де батьки можуть побачити, у яку школу ходитиме їхня дитина.

Як уряд піклується, про школярів, для яких пропонує найближчу школу, так і служби таксі піклуються про своїх клієнтів і намагаються подати таксі якомога швидше. Тут на допомогу теж приходить метод Вороного. Коли ви викликаєте таксі, ви вказуєте ваше місцезнаходження. Компанія повинна знайти машину, яка є ймовірніше найближчою до вас, і передає запит водієві. Місто розбивається на комірки, ядрами яких є машини таксі. Давайте покажемо ваше місцезнаходження літерою А, на малюнку, таксистів, які знаходяться поруч – Боба (регіон B), Керола (C), Дейва (D) і Едіта (Е). Якщо ви знаходитесь всередині комірки B, Боб буде найближчим таксі. Компанія таксі отримує ймовірності близькості. На малюнку, враховуючи відсутність заторів: таксі Боба є найближчим з вірогідністю 51%; таксі Керола з ймовірністю 31%; таксі Дейва з 18% вірогідністю; всі інші з вірогідністю 0%.

Компанія таксі передає запит Бобу. Задача вирішена швидко і з економією часу для клієнта та палива для компанії.

Цікавий приклад з життя, коли ми несвідомо маючи свій особистий простір розбиваємо простір навколо нас на комірки Вороного. Коли ви заходите в ліфт, ви стоїте посередині, рівновіддалено від чотирьох стін. На наступному поверсі заходить ще один пасажир, звісно, ви поступитесь простором. Психологічно і фізично ви розділите простір в ліфті з попутником. На наступному поверсі заходить ще один пасажир, і ви так само розділите простір, тільки вже на три частини. За ядра комірок ми беремо пасажирів ліфту, а особистий простір – за комірки Вороного. Можна зробити висновок: що менший об’єм комірки, то в густішому оточенні вона перебуває, і навпаки – що більший об’єм (коли людина одна у ліфті), то далі об’єкти перебувають одне від одного.

Так само і рослини потребують фізичного простору. Це враховують у садівництві. Наприклад, персикове дерево не проживе більше п’яти років, якщо буде ближче ніж за сім метрів до черешні. Та сторона персикового дерева, яка ближча до вишні чи черешні, починає всихати й відхилятися в іншу сторону. Гарними сусідами для персиків є яблуні та груші. Якщо посадити грушу біля вишні, вона не буде відхилятися, але швидко стане чахлою. Науковий термін для цього явища – алелопатія. Це властивість рослин, грибів, мікроорганізмів виділяти органічні сполуки, які пригнічують проростання, ріст, розвиток і здатність до розмноження інших організмів. Алелопатія може розглядатися як форма екологічної конкуренції між організмами, співвідношення між розміром площі, яку вони займають, та об’ємом рослин. Це дуже важливо не тільки для садівництва, а й для лісничої справи. Важливо знати, який об’єм старих дерев потрібно вирубувати, щоб омолодився ліс, як це вплине на молоді дерева і скільки молодих потрібно залишити, щоб не порушити природний баланс.

Цю проблему вирішили в Каліфорнійському університеті. Там використовують програму для комп’ютерного моделювання й аналізу росту лісів. Програма розроблена професоркою Мариною Гавриловою з Канади із застосуванням діаграми Вороного. Знаючи місце розташування рослин та радіус розповсюдження залежно від виду, за допомогою цієї програми можна вирішити проблеми садівництва.

 Метод мозаїки Вороного допомагає вирішити завдання і в астрономії. Одним із таких завдань є вивчення еволюції галактик та їхнього оточення. Дослідження галактик починається з морфології, тобто опису їх видимих форм і визначення типу за цими формами. Але навіть на першому етапі виникає проблема: не буває однакових галактик. Цю проблему можна порівняти зі складністю класифікації біологічних видів на землі. Проте класифікувати галактики необхідно, оскільки їх надто багато, щоб описувати кожну окремо (лише зафіксованих на сьогодні мільйони). Групування об’єктів в астрономії, як і в біології, є першим кроком для дослідження. Фізичні характеристики, просторовий розподіл, походження часто залежать від типу об’єкта. Тому, виділяючи певний тип галактик, ми окреслюємо фізичні й структурні особливості всіх представників цього типу. Галактики можна грубо розділити на два види: ранні та пізні. Хто з них старший? Для запам’ятовування можна навести приклад з дітьми: рання дитина старша, а пізня – молодша. Ранні галактики мають жовте забарвлення: увесь газ пішов на утворення зірок. Пізні галактики – блакитного кольору, оскільки в них газ іще є. Газ у галактиках – як цегла для зірок. Наприклад, наша галактика Чумацький шлях і сусідня галактика Андромеда (яку часто бачили на заставках користувачі макбуків) є пізніми галактиками, оскільки вони блакитного кольору, а отже, в них є місця зореутворення.

Як це стосується Вороного? Сьогодні є багато телескопів, місія яких – сканувати небо й фіксувати всі об’єкти. Так астрономи отримують координати галактик і відстань до них. Розглядаючи галактики як ядра комірок Вороного, ми отримуємо об’єми цих комірок вже в тривимірному просторі за рахунок двох координат і відстані. Принцип той самий, що і з відпочивальниками у Брайант-Парку. Астрономи помітили, що в тісному оточенні перебувають ранні галактики. Газ, що був у такій галактиці, не тільки пішов на утворення зірок, а ще й «видувся» під тиском інших галактик. Пізні галактики перебувають у комірках із великим об’ємом: біля них немає інших галактик і процес еволюції проходить у своєму темпі. Такі галактики дуже важливі, оскільки завдяки їм можна побачити, як проходить еволюція галактик без впливу інших об’єктів.

Метод мозаїки Вороного застосували для розв’язання чотиристарічної задачі пакування куль, авторкою вирішення якої є українська математикиня Марина В’язовська. У нас є багато куль, і ми хочемо цими кулями заповнити простір. Звичайно, ми не можемо заповнити весь простір, оскільки в куль немає кутів і завжди якась частина простору залишиться порожньою. Потрібно знайти таке розташування куль, за якого вони заповнять якомога більшу частину простору. У двовимірному просторі можна подивитись на розріз упакованих кабелів. У тривимірному просторі це можуть бути помідори, запаковані в ящик. Розв’язання цієї задачі заощаджує витрати на матеріали й оптимізовує виробництво. Марина В’язовська у 2016 році отримала за вирішення задачі одну з найзнаковіших світових премій – премію Салема. Вона розв’язала задачу розміщення куль у восьмивимірному просторі і стала співавторкою розв’язку такої задачі у 24-вимірному просторі. Восьмивимірний простір важливий для передачі даних на різні відстані, наприклад, із космічних станцій на станції прийому на Землі – у такому випадку є ризик наштовхнутись на перешкоди. Уявімо, що восьмивимірний простір – це вісім чисел, які нам потрібно передати. Для уникнення перешкод потрібно розбивати числа на групи й упакувати максимально щільно, щоб передати інформацію з мінімальними втратами.

У гідрології діаграми Вороного використовують для обчислення кількості опадів у районі на основі ряду точкових вимірювань. У цьому застосуванні вони, зазвичай, називаються полігонами Тиссена, на честь американського метеоролога Альфреда Тиссена, який у 1911 році написав роботу про геометричні методи для прогнозування погоди.

Діаграми Вороного широко використовують і в багатьох інших напрямках науки, зокрема в комп’ютерній графіці, геометричному моделюванні, створенні штучного інтелекту, розпізнаванні образів, конструюванні роботів, медицині, радіаційній фізиці, астрофізиці, кристалографії, археології. Починаючи з середини 1970-х років, роботи Вороного використовують фахівці різних галузей практично в усіх країнах Європи, у США, Канаді, Японії, Австралії, Китаї, Новій Зеландії. У корейському Сеулі існує Дослідницький центр діаграм Вороного, з ініціативи якого з 2004 року в різних країнах світу проводяться щорічні конференції, присвячені узагальненням діаграм Вороного та їх використанню.

Простий геометричний метод може бути корисним, врятувати життя, допомогти зрозуміти психологію людей та «поведінку» галактик, передати неушкодженою інформацію або надихати дизайнерів інтер’єрів. Зверніть увагу: можливо, люстра в кав’ярні, у яку ви ходите, нагадує комірки Вороного.

0:00/0:00

Популярні статті

Стаття Суспільство — 27 березня

Як Росія завойовувала вплив у країнах Африки

Стаття Космос - 29 лютого

Куншткамера з Девідом Сперґелом про реліктове випромінювання, НАЯ (НЛО) та співпрацю з українськими науковцями

Стаття Пост правди - 25 березня

Пост правди, епізод 7: Анонімність в телеграмі