Бета-кістяк

${\displaystyle {\boldsymbol {\beta }}}$-кістяк, бета-кістяк або бета-скелет — орієнтований граф, визначений на множині точок на евклідовій площині. Дві точки p і q пов'язані ребром, коли всі кути prq менші від деякого порогу, визначеного параметром ${\displaystyle \beta }$.

Нехай ${\displaystyle \beta }$ — додатне дійсне число, обчислимо кут ${\displaystyle \theta }$ за формулами

${\displaystyle \theta ={\begin{cases}\sin ^{-1}{\frac {1}{\beta }},&&\beta \geqslant 1\\\pi -\sin ^{-1}{\beta },&&\beta \leqslant 1\end{cases}}}$

Для будь-яких двох точок p і q на площині нехай R_pq — множина точок, для яких кут prq більший від ${\displaystyle \theta }$. Тоді R_pq набуває вигляду об'єднання двох відкритих дисків із діаметром ${\displaystyle \beta {d}(p,q)}$ для ${\displaystyle \beta \geqslant 1}$ і ${\displaystyle \theta \leqslant \pi /2}$ і набуває форми перетину двох відкритих дисків діаметра ${\displaystyle d(p,q)/\beta }$ для ${\displaystyle \beta \leqslant 1}$ і ${\displaystyle \theta \geqslant \pi /2}$. Коли ${\displaystyle \beta =1}$, дві формули дають те саме значення, ${\displaystyle \theta =\pi /2}$ і R_pq набуває форми одного відкритого диска з діаметром pq.

${\displaystyle \beta }$-кістяк дискретної множини S точок площини — це неорієнтований граф, який з'єднує дві точки p і q ребром pq, коли R_pq не містить точок S. Тобто ${\displaystyle \beta }$-кістяк є графом порожніх просторів, визначених ділянками R_pq^[1]. Якщо S містить точку r для якої кут prq більший від ${\displaystyle \theta }$, то pq не є ребром ${\displaystyle \beta }$-кістяка. ${\displaystyle \beta }$-кістяк складається з тих пар pq, для яких така точка r існує.

Деякі автори використовують альтернативне визначення, в якому порожні ділянки R_pq для ${\displaystyle \beta >1}$ є не об'єднанням двох дисків, а лінзою, перетином двох дисків із діаметрами ${\displaystyle \beta {d}(pq)}$, таких, що відрізок pq лежить на радіусах обох дисків, так що обидві точки p і q лежать на межі перетину. Як і у випадку ${\displaystyle \beta }$-кістяка, заснованого на колах, заснований на лінзах ${\displaystyle \beta }$-кістяк має ребро pq, коли ділянка R_pq порожня від інших точок. Для цього альтернативного визначення, граф відносних околів є особливим випадком ${\displaystyle \beta }$-кістяка з ${\displaystyle \beta =2}$. Для ${\displaystyle \beta \leqslant 1}$ два визначення збігаються, а для більших значень ${\displaystyle \beta }$ заснований на колах кістяк є подграфом кістяка, заснованого на лінзах.

Одна важлива різниця між заснованими на колах та заснованими на лінзах ${\displaystyle \beta }$-кістяками полягає в тому, що для будь-якої множини точок, які не лежать на одній прямій, завжди існує досить велике значення ${\displaystyle \beta }$, таке, що заснований на колах ${\displaystyle \beta }$-кістяк є порожнім графом. Для контрасту, якщо пара точок p і q має властивість, що для будь-якої точки r один із двох кутів pqr і qpr тупий, то заснований на лінзах ${\displaystyle \beta }$-кістяк міститиме ребро pq незалежно від того, наскільки велике значення ${\displaystyle \beta }$.

Першими ${\displaystyle \beta }$-кістяк визначили Кіркпатрик і Радке^[2] як масштабно інваріантний варіант альфа-форми Едельсбруннера, Кіркпатрика і Зайделя^[3]. Назва ${\displaystyle \beta }$-кістяк відбиває факт, що в деякому сенсі ${\displaystyle \beta }$-кістяк описує форму множини точок так само, як топологічний кістяк описує форму двовимірної ділянки. Також розглянуто декілька узагальнень ${\displaystyle \beta }$-кістяка на графи, визначені іншими порожніми ділянками^[1][4].

Якщо ${\displaystyle \beta }$ змінюється безперервно від 0 до ${\displaystyle \infty }$, засновані на колі ${\displaystyle \beta }$-кістяки утворюють послідовність графів від повного графа до порожнього графа. Спеціальний випадок ${\displaystyle \beta =1}$ веде до графа Габріеля, який, як відомо, містить евклідове мінімальне кістякове дерево. Отже, якщо ${\displaystyle \beta \leqslant 1}$, ${\displaystyle \beta }$-кістяк також містить граф Габріеля і мінімальне кістякове дерево.

Для будь-якої сталої ${\displaystyle \beta }$, для визначення послідовності точкових множин, ${\displaystyle \beta }$-кістяки яких є шляхами довільно великої довжини в одиничному квадраті, можна використати побудову фракталу, який нагадує згладжену версію сніжинки Коха. Тому, на відміну від тісно зв'язаної тріангуляції Делоне, ${\displaystyle \beta }$-кістяки мають необмежений коефіцієнт розтягування і не є геометричними кістяками^[5][6][7].

Простий природний алгоритм, який перевіряє кожну трійку p, q і r на належність точки r ділянці R_pq може побудувати ${\displaystyle \beta }$-кістяк будь-якої множини з n точками за час O(n³).

Коли ${\displaystyle \beta \geqslant 1}$, ${\displaystyle \beta }$-кістяк (у будь-якому визначенні) є підграфом графа Габріеля, який є підграфом тріангуляції Делоне. Якщо pq є ребром тріангуляції Делоне, але не є ребром ${\displaystyle \beta }$-кістяка, то точку r, яка утворює більший кут prq, можна знайти як одну з двох точок, що утворюють трикутник із точками p і q в тріангуляції Делоне. Тому для цих значень ${\displaystyle \beta }$ заснований на колах ${\displaystyle \beta }$-кістяк для множини n точок можна побудувати за час O(n log n) шляхом обчислення тріангуляції Делоне та використовуючи цей тест як фільтр для ребер^[4].

Для ${\displaystyle \beta <1}$ інший алгоритм — Уртадо, Ліотти та Мейєра (Meijer)^[8] — дозволяє побудувати ${\displaystyle \beta }$-кістяк за час O(n²). Жодної кращої межі для часу в гіршому випадку не існує, оскільки для будь-якого фіксованого значення ${\displaystyle \beta }$, меншого від 1, існують множини точок у загальному положенні (невеликі збурення правильного многокутника), для яких ${\displaystyle \beta }$-кістяк є щільним графом із квадратним числом ребер. У тих самих квадратичних часових межах можна обчислити весь ${\displaystyle \beta }$-спектр (послідовність заснованих на колах ${\displaystyle \beta }$-кістяків, отримуваних змінюванням ${\displaystyle \beta }$).

Заснований на колах ${\displaystyle \beta }$-кістяк можна використати в аналізі зображень для відновлення форми двовимірного об'єкта, якщо дано множину точок на межі об'єкта (обчислювальний аналог головоломки «Сполучити точки», де послідовність сполучання точок не задано заздалегідь як частину головоломки, а алгоритм має її обчислити). Хоча, загалом, це вимагає вибору значення параметра ${\displaystyle \beta }$, можна довести, що вибір ${\displaystyle \beta =1{,}7}$ буде правильно відновлювати всю межу будь-якої гладкої поверхні і не створюватиме будь-якого ребра, яке не належить межі, оскільки точки генеруються досить щільно відносно локальної кривини поверхні^[9][10]. Однак в експериментальних тестах менше значення ${\displaystyle \beta =1{,}2}$ було ефективнішим для відновлення карти вулиць за множиною точок, що відображають центральні лінії вулиць у геоінформаційній системі^[11]. Як узагальнення техніки ${\displaystyle \beta }$-кістяка для відновлення поверхонь у тривимірному просторі, див. Hiyoshi, (2007).

Засновані на колах ${\displaystyle \beta }$-кістяки використовували для пошуку графів мінімальної зваженої тріангуляції множини точок — для досить великих значень ${\displaystyle \beta }$ будь-яке ребро ${\displaystyle \beta }$-кістяка гарантовано належить мінімальній зваженій тріангуляції. Якщо ребра, знайдені в такий спосіб, утворюють зв'язний граф на всіх точках, то решта ребер мінімальної зваженої тріангуляції можна знайти за поліноміальний час за допомогою динамічного програмування. Однак, у загальному випадку, задача мінімальної зваженої тріангуляції є NP-складною і підмножина ребер, знайдених у такий спосіб, може не бути зв'язною^[12][13].

${\displaystyle \beta }$-кістяки також застосовують у машинному навчанні для задач геометричної класифікації^[14][15] і в бездротових ad-hoc-мережах як механізм контролю складності мережі шляхом вибору підмножини пар бездротових станцій, які можуть спілкуватися між собою^[16].