Бета-кістяк

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

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

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

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

Нехай ${\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. Якщо S містить точку r для якої кут prq більший від ${\displaystyle \theta }$, то pq не є ребром ${\displaystyle \beta }$-кістяка. ${\displaystyle \beta }$-кістяк складається з тих пар pq, для яких така точка r існує.

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

Деякі автори використовують альтернативне визначення, в якому порожні ділянки R_pq для ${\displaystyle \beta >1}$ є не об'єднанням двох дисків, а ^[en], перетином двох дисків із діаметрами ${\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 }$-кістяк визначили Кіркпатрик і Радке як масштабно інваріантний варіант альфа-форми Едельсбруннера, Кіркпатрика і Зайделя. Назва ${\displaystyle \beta }$-кістяк відбиває факт, що в деякому сенсі ${\displaystyle \beta }$-кістяк описує форму множини точок так само, як топологічний кістяк описує форму двовимірної ділянки. Також розглянуто декілька узагальнень ${\displaystyle \beta }$-кістяка на графи, визначені іншими порожніми ділянками.

Властивості

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

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

Алгоритми

Простий природний алгоритм, який перевіряє кожну трійку 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) шляхом обчислення тріангуляції Делоне та використовуючи цей тест як фільтр для ребер.

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

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

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

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

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

Примітки

1. Cardinal, Collette, Langerman, 2009.
2. Kirkpatrick, Radke, 1985.
3. Edelsbrunner, Kirkpatrick, Seidel, 1983.
4. Veltkamp, 1992.
5. Eppstein, 2002.
6. Bose, Devroye, Evans, Kirkpatrick, 2002.
7. Wang, Li, Moaveninejad, Wang, Song, 2003.
8. Hurtado, Liotta, Meijer, 2003.
9. Amenta, Bern, Eppstein, 1998.
10. O'Rourke, 2000.
11. Radke, Flodmark, 1999.
12. Keil, 1994.
13. Cheng, Xu, 2001.
14. Zhang, King, 2002.
15. Toussaint, 2005.
16. Bhardwaj, Misra, Xue, 2005.

Література

• 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 ${\displaystyle \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 ${\displaystyle \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 // . — 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 ${\displaystyle \beta }$-skeletons // Proc. 15th Canadian Conference on Computational Geometry (CCCG 2003). — 2003. — С. 35–38.
• Wan Zhang, Irwin King. Locating support vectors via ${\displaystyle \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.