Бета-кістяк

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

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

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

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

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

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

$\beta$-кістяк дискретної множини S точок площини — це неорієнтований граф, який з'єднує дві точки p і q ребром pq, коли R_pq не містить точок S. Тобто $\beta$-кістяк є графом порожніх просторів, визначених ділянками R_pq. Якщо 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 \leqslant 1$ два визначення збігаються, а для більших значень $\beta$ заснований на колах кістяк є подграфом кістяка, заснованого на лінзах.

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

Історія

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

Властивості

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

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

Алгоритми

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

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

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

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

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

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

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

Література

• Nina Amenta, Marshall Bern, David Eppstein. The crust and the beta-skeleton: combinatorial curve reconstruction // Graphical Models & Image Processing. — 1998. — Т. 60/2, вип. 2. — С. 125–135. Архівовано з джерела 22 березня 2006..
• Manvendu Bhardwaj, Satyajayant Misra, Guoliang Xue. Workshop on High Performance Switching and Routing (HPSR 2005), Hong Kong, China. — 2005. Архівовано з джерела 7 червня 2011..
• Prosenjit Bose, Luc Devroye, William Evans, David G. Kirkpatrick. On the spanning ratio of Gabriel graphs and $\beta$-skeletons // LATIN 2002: Theoretical Informatics. — Springer-Verlag, 2002. — Т. 2286. — С. 77–97. — (Lecture Notes in Computer Science) — DOI:10.1007/3-540-45995-2_42.
• Jean Cardinal, Sébastian Collette, Stefan Langerman. Empty region graphs // Computational Geometry Theory & Applications. — 2009. — Т. 42, вип. 3. — С. 183–195. — DOI:10.1016/j.comgeo.2008.09.003.
• Siu-Wing Cheng, Yin-Feng Xu. On $\beta$-skeleton as a subgraph of the minimum weight triangulation // Theoretical Computer Science. — 2001. — Т. 262, вип. 1–2. — С. 459–471. — DOI:10.1016/S0304-3975(00)00318-2..
• Herbert Edelsbrunner, David G. Kirkpatrick, Raimund Seidel. On the shape of a set of points in the plane // IEEE Transactions on Information Theory. — 1983. — Т. 29, вип. 4. — С. 551–559. — DOI:10.1109/TIT.1983.1056714.
• David Eppstein. Beta-skeletons have unbounded dilation // Computational Geometry Theory & Applications. — 2002. — Т. 23, вип. 1. — С. 43–52. — arXiv:cs.CG/9907031. — DOI:10.1016/S0925-7721(01)00055-4..
• Hiyoshi H. Greedy beta-skeleton in three dimensions // Proc. 4th International Symposium on Voronoi Diagrams in Science and Engineering (ISVD 2007). — 2007. — С. 101–109. — DOI:10.1109/ISVD.2007.27..
• Ferran Hurtado, Giuseppe Liotta, Henk Meijer. Optimal and suboptimal robust algorithms for proximity graphs // Computational Geometry Theory & Applications. — 2003. — Т. 25, вип. 1–2. — С. 35–49. — DOI:10.1016/S0925-7721(02)00129-3.
• J. Mark Keil. Computing a subgraph of the minimum weight triangulation // Computational Geometry Theory & Applications. — 1994. — Т. 4, вип. 1. — С. 18–26. — DOI:10.1016/0925-7721(94)90014-0..
• David G. Kirkpatrick, John D. Radke. A framework for computational morphology // Computational Geometry. — Amsterdam : North-Holland, 1985. — Т. 2. — С. 217–248. — (Machine Intelligence and Pattern Recognition).
• Joseph O'Rourke. Computational Geometry Column 38 // SIGACT News. — 2000. — Т. 31, вип. 1. — С. 28–30. — arXiv:cs.CG/0001025. — DOI:10.1145/346048.346050.
• John D. Radke, Anders Flodmark. The use of spatial decompositions for constructing street centerlines // Geographic Information Sciences. — 1999. — Т. 5, вип. 1. — С. 15–23.
• Godfried Toussaint. Geometric proximity graphs for improving nearest neighbor methods in instance-based learning and data mining // International Journal of Computational Geometry and Applications. — 2005. — Т. 15, вип. 2. — С. 101–150. — DOI:10.1142/S0218195905001622.
• Remko C. Veltkamp. The γ-neighborhood graph // Computational Geometry Theory & Applications. — 1992. — Т. 1, вип. 4. — С. 227–246. — DOI:10.1016/0925-7721(92)90003-B.
• Weizhao Wang, Xiang-Yang Li, Kousha Moaveninejad, Yu Wang, Wen-Zhan Song. The spanning ratio of $\beta$-skeletons // Proc. 15th Canadian Conference on Computational Geometry (CCCG 2003). — 2003. — С. 35–38.
• Wan Zhang, Irwin King. Locating support vectors via $\beta$-skeleton technique // Proc. Proceedings of the 9th International Conference on Neural Information Processing (ICONIP'02), Orchid Country Club, Singapore, November 18-22, 2002. — 2002. — С. 1423–1427.