Бета-кістяк

Заснований на колах 1.1-кістяк (жирні темні ребра) і 0.9-кістяк (світлі пунктирні сині ребра) множини випадкових 100 точок у квадраті.

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

Визначення на основі кіл

Порожні простори $R_{pq}$, що визначають заснований на колах $\beta$-кістяк. Зліва: $\beta <1$. Посередині: $\beta =1$. Праворуч: $\beta >1$.

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

$\theta =\{\begin{array}{ccc}{\sin }^{-1}\frac{1}{\beta },& & \beta ⩾1\\ \pi -{\sin }^{-1}\beta ,& & \beta ⩽1\end{array}$

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

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

Визначення на основі лінз

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

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

Історія

Першими $\beta$-кістяк визначили Кіркпатрик і РадкеШаблон:Sfn як масштабно інваріантний варіант альфа-форми Едельсбруннера, Кіркпатрика і ЗайделяШаблон:Sfn. Назва $\beta$-кістяк відбиває факт, що в деякому сенсі $\beta$-кістяк описує форму множини точок так само, як топологічний кістяк описує форму двовимірної ділянки. Також розглянуто декілька узагальнень $\beta$-кістяка на графи, визначені іншими порожніми ділянкамиШаблон:SfnШаблон:Sfn.

Властивості

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

Для будь-якої сталої $\beta$, для визначення послідовності точкових множин, $\beta$-кістяки яких є шляхами довільно великої довжини в одиничному квадраті, можна використати побудову фракталу, який нагадує згладжену версію сніжинки Коха. Тому, на відміну від тісно зв'язаної тріангуляції Делоне, $\beta$-кістяки мають необмежений Шаблон:Не перекладено і не є геометричними кістякамиШаблон:SfnШаблон:SfnШаблон:Sfn.

Алгоритми

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

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

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

Застосування

Заснований на колах $\beta$-кістяк можна використати в Шаблон:Не перекладено для відновлення форми двовимірного об'єкта, якщо дано множину точок на межі об'єкта (обчислювальний аналог головоломки Шаблон:Не перекладено, де послідовність сполучання точок не задано заздалегідь як частину головоломки, а алгоритм має її обчислити). Хоча, загалом, це вимагає вибору значення параметра $\beta$, можна довести, що вибір $\beta =1,7$ буде правильно відновлювати всю межу будь-якої гладкої поверхні і не створюватиме будь-якого ребра, яке не належить межі, оскільки точки генеруються досить щільно відносно локальної кривини поверхніШаблон:SfnШаблон:Sfn. Однак в експериментальних тестах менше значення $\beta =1,2$ було ефективнішим для відновлення карти вулиць за множиною точок, що відображають центральні лінії вулиць у геоінформаційній системіШаблон:Sfn. Як узагальнення техніки $\beta$-кістяка для відновлення поверхонь у тривимірному просторі, див. Шаблон:Harvtxt.

Засновані на колах $\beta$-кістяки використовували для пошуку графів Шаблон:Не перекладено множини точок — для досить великих значень $\beta$ будь-яке ребро $\beta$-кістяка гарантовано належить мінімальній зваженій тріангуляції. Якщо ребра, знайдені в такий спосіб, утворюють зв'язний граф на всіх точках, то решта ребер мінімальної зваженої тріангуляції можна знайти за поліноміальний час за допомогою динамічного програмування. Однак, у загальному випадку, задача мінімальної зваженої тріангуляції є NP-складною і підмножина ребер, знайдених у такий спосіб, може не бути зв'язноюШаблон:SfnШаблон:Sfn.

$\beta$-кістяки також застосовують у машинному навчанні для задач геометричної класифікаціїШаблон:SfnШаблон:Sfn і в бездротових ad-hoc-мережах як механізм контролю складності мережі шляхом вибору підмножини пар бездротових станцій, які можуть спілкуватися між собоюШаблон:Sfn.

Література

• Шаблон:Стаття.
• Шаблон:Стаття.
• Шаблон:Книга
• Шаблон:Стаття
• Шаблон:Стаття.
• Шаблон:Стаття
• Шаблон:Стаття.
• Шаблон:Книга.
• Шаблон:Стаття
• Шаблон:Стаття.
• Шаблон:Книга.
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Книга
• Шаблон:Книга