Spotlight #60 – Обчислювальна геометрія — упаковка сфер, криві, що заповнюють простір, і тріангуляція

I. Упаковка сфер — гіпотеза Кеплера й ГЦК-ґратка

1611 року Йоганн Кеплер стверджував, що найефективніший спосіб упакувати однакові сфери — це розташування, яке використовують продавці овочів, складаючи апельсини: гексагонально щільно упаковані шари, кожен зі зсувом, щоб лягти в западини шару під ним. Це дає щільність упаковки:

η = π / (3√2)  ≈  0.7405

Тобто близько 74% простору зайнято сферами, а 26% залишається порожнечею. Ту саму щільність дають гранецентрована кубічна (ГЦК) ґратка й гексагонально щільно упакований (ГЩУ) розподіл; різниця в тому, як складено послідовні шари (ABCABC проти ABABAB). Гіпотеза Кеплера залишалася недоведеною майже чотири століття. Виклик полягав не лише в геометричній інтуїції, а в строгому виключенні кожного можливого нерегулярного розташування, яке могло б потай упаковувати щільніше.

Доведення Гейлза-Фергюсона та проєкт Flyspeck

Томас Гейлз і Семюел Фергюсон оголосили про доведення 1998 року, звівши гіпотезу до скінченної, але величезної задачі лінійного програмування, а потім розв'язавши її обчислювально. Поданий рукопис, супроводжуваний гігабайтами комп'ютерного коду, був прийнятий 2005 року журналом Annals of Mathematics — але рецензенти відомо повідомили, що вони «на 99% впевнені» в правильності, не маючи змоги перевірити вручну кожен обчислювальний крок. Це спонукало проєкт Flyspeck: десятилітнє зусилля створити повністю комп'ютерно верифіковане формальне доведення, завершене 2014 року з використанням асистентів доведення HOL Light та Isabelle. Flyspeck став віхою у формальній математиці, продемонструвавши, що велику відкриту проблему можна розв'язати з абсолютною логічною певністю за допомогою машини.

Випадкова упаковка — просто засипання сфер у контейнер — досягає максимальної щільності приблизно 0.64 (межа «випадкової щільної упаковки»). Розрив між 0.64 і 0.7405 має величезні практичні наслідки: він визначає пористість фармацевтичних таблеток, проникність ґрунту та провідність композитних матеріалів. Симуляція дозволяє безпосередньо порівняти ці режими.

II. Крива Гілберта — лінія, що заповнює квадрат

1890 року Джузеппе Пеано вразив математичний світ, побудувавши неперервну криву, що проходила крізь кожну точку одиничного квадрата — криву з двовимірним образом з одновимірного параметра. Наступного року Давід Гілберт дав чистішу, геометрично прозорішу побудову. Кожна ітерація кривої Гілберта ділить квадрат на чотири квадранти, з'єднує їх U-подібним шляхом і рекурсивно застосовує те саме правило всередині кожного квадранта, обертаючи й відображаючи за потреби.

Гранична крива має розмірність Хаусдорфа рівно 2, і саме тому вона заповнює площину: це не крива в інтуїтивному сенсі, а фрактальний об'єкт, що розмиває межу між лінією й площею. Формальне твердження полягає в тому, що існує неперервна сюр'єкція з [0,1] на [0,1]², спростовуючи інтуїцію, що криві й квадрати повинні мати різні «розміри» нескінченності точок.

Локальність даних і кеш

Найцінніша властивість кривої Гілберта — її локальність: точки, близькі одна до одної вздовж 1D-параметра, зазвичай близькі одна до одної й у 2D-просторі. Обернене не зовсім вірне (деякі сусідні 2D-точки далеко одна від одної на кривій), але кореляція достатньо сильна, щоб її використовувати в обчисленнях. Геоінформаційні системи використовують індекси кривої Гілберта для сортування просторових даних так, щоб сусідні об'єкти зазвичай лежали в тому самому блоці диска чи рядку кешу. Коли запит вилучає всі точки в межах обмежувального прямокутника, просторово впорядковані дані спричиняють значно менше промахів кешу, ніж наївне впорядкування за рядками.

Механізми баз даних (включно з Google Bigtable та його опенсорсними наступниками) використовують індекси Гілберта для кластеризації пов'язаних рядків на диску. Алгоритми стиснення зображень використовують відображення 2D-в-1D (пов'язані з кривою Гілберта) для кодових книг квантування. Навіть контролери пам'яті DRAM експериментували з упорядкуваннями Гілберта для покращення багатопоточних просторових шаблонів доступу. Ідея, що топологія кривої може оптимізувати продуктивність заліза, — прекрасний приклад того, як абстрактна математика знаходить несподіване інженерне застосування.

III. Спіраль Улама — прихована геометрія простих чисел

1963 року Станіслав Улам сидів на нудній нараді й почав малювати: він написав 1 у центрі, потім розкрутив цілі числа назовні квадратною спіраллю й обвів прості числа. Отримана діаграма, розширена до тисяч цілих чисел, показує безсумнівні діагональні смуги — лінії, вздовж яких прості числа групуються значно щільніше, ніж очікується від випадковості. Каракулі Улама стали невеликою сенсацією, коли їх опублікував Scientific American.

Пояснення криється в квадратичних поліномах. Кожна діагональ спіралі відповідає поліному вигляду 4n² + bn + c для фіксованих b і c. Деякі поліноми генерують прості числа з винятково високою частотою. Знаменита формула Ейлера n² + n + 41 дає прості числа для всіх n від 0 до 39 — сорок послідовних простих чисел. У спіралі Улама цей поліном вимальовує яскраву діагональну смугу. Гіпотези Гарді-Літлвуда про прості числа (гіпотеза B, 1923) дають евристичне пояснення: щільність простих чисел, породжених поліномом, пов'язана з тим, наскільки часто він уникає подільності на малі прості числа, кількісно вираженою добутком локальних множників, що зветься особливим рядом.

Чому не існує доведення

Попри чіткий візуальний узор, жоден квадратичний поліном не доведено породжує нескінченно багато простих чисел. Теорема Діріхле гарантує нескінченно багато простих чисел у лінійних прогресіях an + b (коли gcd(a,b) = 1), але аналог для квадратичних — четверта проблема Ландау — залишається відкритим. Спіраль Улама, отже, візуалізує одне з найглибших відкритих питань теорії чисел: нерегулярний розподіл простих чисел одночасно локально упорядкований і глобально загадковий.

IV. Тріангуляція Делоне — найкраща трикутна сітка

Маючи набір точок на площині, багато можливих тріангуляцій з'єднують їх у трикутники, що не перекриваються. Тріангуляція Делоне — та єдина, що максимізує мінімальний внутрішній кут серед усіх трикутників — еквівалентно, вона уникає «скалкоподібних» трикутників настільки, наскільки це геометрично можливо. Визначальний критерій — властивість порожнього описаного кола: для кожного трикутника в тріангуляції його описане коло не містить жодної іншої точки набору всередині.

Тріангуляція Делоне — геометрично двоїста до діаграми Вороного: якщо з'єднати центри сусідніх комірок Вороного (комірок, що мають спільне ребро), отримаємо тріангуляцію Делоне. Ця двоїстість означає, що обчислення однієї дає іншу, і пояснює, чому тріангуляція Делоне розбиває простір у найбільш «природний» спосіб відносно заданого розподілу точок.

Алгоритм Бові-Ватсона та застосування

Алгоритм Бові-Ватсона будує тріангуляцію інкрементально. Почніть із супертрикутника, що містить усі точки. Вставляйте кожну нову точку p: знайдіть усі трикутники, чиє описане коло містить p («погані» трикутники); видаліть їх, утворивши багатокутну діру; ретріангулюйте діру, з'єднавши всі її граничні ребра з p. Алгоритм виконується за очікуваний час O(n log n) і простий у реалізації, що пояснює його поширеність у програмному забезпеченні для генерації сіток.

Застосування охоплюють дивовижний діапазон. У методі скінченних елементів якість елемента (а отже, й чисельна точність) безпосередньо пов'язана з мінімальним кутом, що робить Делоне типовою початковою сіткою. Програмне забезпечення моделювання рельєфу тріангулює нерегулярні хмари точок геодезичних вимірювань у моделі TIN (тріангульована нерегулярна мережа). Методи геопросторової інтерполяції на кшталт інтерполяції природних сусідів використовують структуру Делоне для визначення ваг. Навіть обчислювальна гідродинаміка використовує сітки Делоне як відправну точку перед подальшими алгоритмами уточнення (алгоритм Рупперта, алгоритми Чу), що накладають обмеження на кут і щільність.

V. Маршуючі квадрати — вилучення контурів зі скалярних полів

Алгоритм маршуючих квадратів вилучає ізолінії — лінії, вздовж яких скалярне поле дорівнює заданому порогу — з регулярної сітки. Для кожної комірки сітки кожен із чотирьох кутів або вище, або нижче ізозначення. Існує 2⁴ = 16 можливих конфігурацій кутів, і кожна конфігурація відображається на конкретний набір відрізків ліній, що перетинають ребра комірки. Зберігаючи ці відображення в таблиці пошуку, алгоритм «маршує» крізь кожну комірку й збирає відповідні відрізки в контурні лінії.

Два з 16 випадків (випадки 5 і 10) неоднозначні: обидві пари діагональних кутів мають однаковий знак, тож існують дві однаково валідні топології контуру. Стандартне розв'язання вибирає скалярне значення в центрі комірки: якщо центр вище ізозначення, контур утворює дві окремі криві (випадок «розділення»); якщо нижче — контур утворює перетин у сідловій точці. Неправильне розв'язання неоднозначних випадків призводить до топологічних помилок — контурів, що самоперетинаються або залишають розриви.

Від 2D до 3D: маршуючі куби

3D-узагальнення, маршуючі куби (Лоренсен і Клайн, 1987), працює з кубічними вокселями з вісьмома кутами, даючи 2⁸ = 256 конфігурацій, зведених до 15 унікальних випадків через симетрію. Це робочий алгоритм медичної візуалізації: КТ- та МРТ-сканери створюють 3D-скалярні поля (одиниці Гаунсфілда для щільності тканини), а маршуючі куби вилучають поверхні органів на конкретних порогах щільності. Отримані трикутні сітки можна надрукувати на 3D-принтері як анатомічні моделі, імпортувати в програмне забезпечення планування операцій або використати для планування променевої терапії. Практично кожна ізоповерхня, яку ви коли-небудь бачили у науковій візуалізації, була створена цим алгоритмом чи одним з його нащадків.