# Beta skeleton

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Beta_skeleton
> Markdown URL: https://mediated.wiki/source/Beta_skeleton.md
> Source: https://en.wikipedia.org/wiki/Beta_skeleton
> Source revision: 1335628873
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

thumb|300px|The circle-based 1.1-skeleton (heavy dark edges) and 0.9-skeleton (light dashed blue edges) of a set of 100 random points in a square.
In [computational geometry](/source/computational_geometry) and [geometric graph theory](/source/geometric_graph_theory), a '''''β''-skeleton''' or '''beta skeleton''' is an [undirected graph](/source/undirected_graph) defined from a set of points in the [Euclidean plane](/source/Euclidean_plane). Two points ''p'' and ''q'' are connected by an edge whenever all the angles ''prq'' are sharper than a threshold determined from the numerical parameter ''β''.

==Circle-based definition==
thumb|The empty regions ''R''<sub>''pq''</sub> defining the circle-based ''β''-skeleton. Left: ''β''&nbsp;<&nbsp;1. Center: ''β''&nbsp;=&nbsp;1. Right: ''β''&nbsp;>&nbsp;1.
Let ''β'' be a positive [real number](/source/real_number), and calculate an angle ''θ'' using the formulas

:<math>\theta = \begin{cases} \sin^{-1} \frac{1}{\beta}, & \text{if }\beta \ge 1 \\ \pi - \sin^{-1}{\beta}, & \text{if }\beta\le 1\end{cases}</math>

For any two points ''p'' and ''q'' in the plane, let ''R''<sub>''pq''</sub> be the set of points for which angle ''prq'' is greater than&nbsp;''θ''. Then ''R''<sub>''pq''</sub> takes the form of a union of two open disks with diameter ''βd''(''p'',''q'') for ''β''&nbsp;≥&nbsp;1 and ''θ''&nbsp;≤&nbsp;π/2, and it takes the form of the intersection of two open disks with diameter ''d''(''p'',''q'')/''β'' for ''β''&nbsp;≤&nbsp;1 and ''θ''&nbsp;≥&nbsp;π/2. When ''β''&nbsp;=&nbsp;1 the two formulas give the same value ''θ''&nbsp;=&nbsp;π/2, and ''R''<sub>''pq''</sub> takes the form of a single open disk with ''pq'' as its diameter.

The ''β''-skeleton of a [discrete set](/source/Isolated_point) ''S'' of points in the plane is the [undirected graph](/source/undirected_graph) that connects two points ''p'' and ''q'' with an edge ''pq'' whenever ''R''<sub>''pq''</sub> contains no points of ''S''. That is, the ''β''-skeleton is the empty region graph defined by the regions ''R''<sub>''pq''</sub>.<ref name="ccl">{{harvtxt|Cardinal|Collette|Langerman|2009}}.</ref> When ''S'' contains a point ''r'' for which angle ''prq'' is greater than ''θ'', then ''pq'' is not an edge of the ''β''-skeleton; the ''β''-skeleton consists of those pairs ''pq'' for which no such point ''r'' exists.

==Lune-based definition==
Some authors use an alternative definition in which the empty regions ''R''<sub>''pq''</sub> for ''β''&nbsp;>&nbsp;1 are not unions of two disks but rather [lenses](/source/Lens_(geometry)) (more often called in this context "[lunes](/source/Lune_(mathematics))"), intersections of two congruent disks with diameter ''βd''(''pq''), such that line segment ''pq'' lies on a radius of both disks and such that the points ''p'' and ''q'' both lie on the boundary of the intersection. As with the circle-based ''β''-skeleton, the lune-based ''β''-skeleton has an edge ''pq'' whenever region ''R''<sub>''pq''</sub> is empty of other input points. For this alternative definition, the [relative neighborhood graph](/source/relative_neighborhood_graph) is a special case of a ''β''-skeleton with ''β''&nbsp;=&nbsp;2. The two definitions coincide for ''β''&nbsp;≤&nbsp;1, and for larger values of ''β'' the circle-based skeleton is a [subgraph](/source/Glossary_of_graph_theory) of the lune-based skeleton.

One important difference between the circle-based and lune-based ''β''-skeletons is that, for any point set that does not lie on a single line, there always exists a sufficiently large value of ''β'' such that the circle-based ''β''-skeleton is the [empty graph](/source/empty_graph). In contrast, if a pair of points ''p'' and ''q'' has the property that, for all other points ''r'', one of the two angles ''pqr'' and ''qpr'' is obtuse, then the lune-based ''β''-skeleton will contain edge ''pq'' no matter how large ''β'' is.

==History==
''β''-skeletons were first defined by {{harvtxt|Kirkpatrick|Radke|1985}} as a [scale-invariant](/source/Scale_invariance) variation of the [alpha shape](/source/alpha_shape)s of {{harvtxt|Edelsbrunner|Kirkpatrick|Seidel|1983}}. The name, "''β''-skeleton", reflects the fact that in some sense the ''β''-skeleton describes the shape of a set of points in the same way that a [topological skeleton](/source/topological_skeleton) describes the shape of a two-dimensional region. Several generalizations of the ''β''-skeleton to graphs defined by other empty regions have also been considered.<ref name="ccl"/><ref name="v"/>

==Properties==
If ''β'' varies continuously from 0 to ∞, the circle-based ''β''-skeletons form a sequence of graphs extending from the [complete graph](/source/complete_graph) to the [empty graph](/source/empty_graph). The special case ''β''&nbsp;=&nbsp;1 leads to the [Gabriel graph](/source/Gabriel_graph), which is known to contain the [Euclidean minimum spanning tree](/source/Euclidean_minimum_spanning_tree); therefore, the ''β''-skeleton also contains the Gabriel graph and the minimum spanning tree whenever ''β''&nbsp;≤&nbsp;1.

For any constant ''β'', a [fractal](/source/fractal) construction resembling a flattened version of the [Koch snowflake](/source/Koch_snowflake) can be used to define a sequence of point sets whose ''β''-skeletons are paths of arbitrarily large length within a unit square. Therefore, unlike the closely related [Delaunay triangulation](/source/Delaunay_triangulation), ''β''-skeletons have unbounded [stretch factor](/source/stretch_factor) and are not [geometric spanner](/source/geometric_spanner)s.<ref>{{harvtxt|Eppstein|2002}}; {{harvtxt|Bose|Devroye|Evans|Kirkpatrick|2002}}; {{harvtxt|Wang|Li|Moaveninejad|Wang|2003}}.</ref>

==Algorithms==
A [naïve algorithm](/source/na%C3%AFve_algorithm) that tests each triple ''p'', ''q'', and ''r'' for membership of ''r'' in the region ''R''<sub>''pq''</sub> can construct the ''β''-skeleton of any set of ''n'' points in time O(''n''<sup>3</sup>).

When ''β''&nbsp;≥&nbsp;1, the ''β''-skeleton (with either definition) is a subgraph of the Gabriel graph, which is a subgraph of the [Delaunay triangulation](/source/Delaunay_triangulation). If ''pq'' is an edge of the Delaunay triangulation that is not an edge of the ''β''-skeleton, then a point ''r'' that forms a large angle ''prq'' can be found as one of the at most two points forming a triangle with ''p'' and ''q'' in the Delaunay triangulation. Therefore, for these values of ''β'', the circle-based ''β''-skeleton for a set of ''n'' points can be constructed in time O(''n''&nbsp;log&nbsp;''n'') by computing the Delaunay triangulation and using this test to filter its edges.<ref name="v">{{harvtxt|Veltkamp|1992}}.</ref>

For ''β''&nbsp;<&nbsp;1, a different algorithm of {{harvtxt|Hurtado|Liotta|Meijer|2003}} allows the construction of the ''β''-skeleton in time O(''n''<sup>2</sup>). No better worst-case time bound is possible because, for any fixed value of ''β'' smaller than one, there exist point sets in general position (small perturbations of a [regular polygon](/source/regular_polygon)) for which the ''β''-skeleton is a [dense graph](/source/dense_graph) with a quadratic number of edges. In the same quadratic time bound, the entire ''β''-spectrum (the sequence of circle-based ''β''-skeletons formed by varying ''β'') may also be calculated.

==Applications==
The circle-based ''β''-skeleton may be used in [image analysis](/source/image_analysis) to reconstruct the shape of a two-dimensional object, given a set of sample points on the boundary of the object (a computational form of the [connect the dots](/source/connect_the_dots) puzzle where the sequence in which the dots are to be connected must be deduced by an algorithm rather than being given as part of the puzzle). Although, in general, this requires a choice of the value of the parameter ''β'', it is possible to prove that the choice ''β''&nbsp;=&nbsp;1.7 will correctly reconstruct the entire boundary of any smooth surface, and not generate any edges that do not belong to the boundary, as long as the samples are generated sufficiently densely relative to the local [curvature](/source/curvature) of the surface.<ref>{{harvtxt|Amenta|Bern|Eppstein|1998}}; {{harvtxt|O'Rourke|2000}}.</ref> However in experimental testing a lower value, ''β''&nbsp;=&nbsp;1.2, was more effective for reconstructing street maps from sets of points marking the center lines of streets in a [geographic information system](/source/geographic_information_system).<ref>{{harvtxt|Radke|Flodmark|1999}}.</ref> For generalizations of the ''β''-skeleton technique to reconstruction of surfaces in three dimensions, see {{harvtxt|Hiyoshi|2007}}.

Circle-based ''β''-skeletons have been used to find subgraphs of the [minimum weight triangulation](/source/minimum_weight_triangulation) of a point set: for sufficiently large values of ''β'', every ''β''-skeleton edge can be guaranteed to belong to the minimum weight triangulation. If the edges found in this way form a [connected graph](/source/connected_graph) on all of the input points, then the remaining minimum weight triangulation edges may be found in [polynomial time](/source/polynomial_time) by [dynamic programming](/source/dynamic_programming). However, in general the minimum weight triangulation problem is NP-hard, and the subset of its edges found in this way may not be connected.<ref>{{harvtxt|Keil|1994}}; {{harvtxt|Cheng|Xu|2001}}.</ref>

''β''-skeletons have also been applied in [machine learning](/source/machine_learning) to solve geometric [classification](/source/Statistical_classification) problems<ref>{{harvtxt|Zhang|King|2002}}; {{harvtxt|Toussaint|2005}}.</ref> and in [wireless ad hoc network](/source/wireless_ad_hoc_network)s as a mechanism for controlling communication complexity by choosing a subset of the pairs of wireless stations that can communicate with each other.<ref>{{harvtxt|Bhardwaj|Misra|Xue|2005}}.</ref>

==Notes==
{{reflist|2}}

==References==
{{refbegin|30em}}
*{{citation
 | last1 = Amenta
 | first1 = Nina
 | author1-link = Nina Amenta
 | last2 = Bern
 | first2 = Marshall
 | last3 = Eppstein
 | first3 = David
 | author3-link = David Eppstein
 | issue = 2
 | journal = Graphical Models and Image Processing
 | pages = 125–135
 | title = The crust and the beta-skeleton: combinatorial curve reconstruction
 | url = http://www.cs.utexas.edu/users/amenta/pubs/crust.ps.gz
 | volume = 60/2
 | year = 1998
 | doi = 10.1006/gmip.1998.0465
 | bibcode = 1998GMIP...60..125A
 | s2cid = 6301659
 | url-status = dead
 | archiveurl = https://web.archive.org/web/20060322023334/http://www.cs.utexas.edu/users/amenta/pubs/crust.ps.gz
 | archivedate = 2006-03-22
 }}.
*{{citation
 | last1 = Bhardwaj
 | first1 = Manvendu
 | last2 = Misra
 | first2 = Satyajayant
 | last3 = Xue
 | first3 = Guoliang
 | year = 2005
 | contribution = Distributed topology control in wireless ad hoc networks using ß-skeleton
 | title = Workshop on High Performance Switching and Routing (HPSR 2005), Hong Kong, China
 | url = http://www.public.asu.edu/~ssatyaja/papers/hpsr05.pdf
 | archive-url = https://web.archive.org/web/20110607105348/http://www.public.asu.edu/~ssatyaja/papers/hpsr05.pdf
 | url-status = dead
 | archive-date = 2011-06-07
 }}.
*{{citation
 | last1 = Bose | first1 = Prosenjit | author1-link = Jit Bose
 | last2 = Devroye | first2 = Luc
 | last3 = Evans | first3 = William
 | last4 = Kirkpatrick | first4 = David G. | author4-link = David G. Kirkpatrick
 | contribution = On the spanning ratio of Gabriel graphs and ''β''-skeletons
 | doi = 10.1007/3-540-45995-2_42
 | pages = 77–97
 | publisher = Springer-Verlag
 | series = Lecture Notes in Computer Science
 | title = LATIN 2002: Theoretical Informatics
 | volume = 2286
 | year = 2002| isbn = 978-3-540-43400-9 }}.
*{{citation
 | last1 = Cardinal | first1 = Jean
 | last2 = Collette | first2 = Sébastian
 | last3 = Langerman | first3 = Stefan | author3-link = Stefan Langerman
 | doi = 10.1016/j.comgeo.2008.09.003
 | issue = 3
 | journal = Computational Geometry Theory & Applications
 | pages = 183–195
 | title = Empty region graphs
 | volume = 42
 | year = 2009| doi-access = 
 }}.
*{{citation
 | last1 = Cheng | first1 = Siu-Wing
 | last2 = Xu | first2 = Yin-Feng
 | doi = 10.1016/S0304-3975(00)00318-2
 | issue = 1–2
 | journal = Theoretical Computer Science
 | pages = 459–471
 | title = On ''β''-skeleton as a subgraph of the minimum weight triangulation
 | volume = 262
 | year = 2001| doi-access = free
 }}.
*{{citation
 | last1 = Edelsbrunner | first1 = Herbert | author1-link = Herbert Edelsbrunner
 | last2 = Kirkpatrick | first2 = David G. | author2-link = David G. Kirkpatrick
 | last3 = Seidel | first3 = Raimund | author3-link = Raimund Seidel
 | doi = 10.1109/TIT.1983.1056714
 | issue = 4
 | journal = IEEE Transactions on Information Theory
 | pages = 551–559
 | title = On the shape of a set of points in the plane
 | volume = 29
 | year = 1983 | bibcode = 1983ITIT...29..551E }}.
*{{citation
 | last = Eppstein | first = David | author-link = David Eppstein
 | doi = 10.1016/S0925-7721(01)00055-4
 | issue = 1
 | journal = Computational Geometry Theory & Applications
 | pages = 43–52
 | title = Beta-skeletons have unbounded dilation
 | volume = 23
 | year = 2002
 | arxiv = cs.CG/9907031| s2cid = 1617451 }}.
*{{citation
 | last = Hiyoshi | first = H.
 | contribution = Greedy beta-skeleton in three dimensions
 | doi = 10.1109/ISVD.2007.27
 | pages = 101–109
 | title = Proc. 4th International Symposium on Voronoi Diagrams in Science and Engineering (ISVD 2007)
 | year = 2007| isbn = 978-0-7695-2869-4
 | s2cid = 23189942
 }}.
*{{citation
 | last1 = Hurtado | first1 = Ferran | author1-link = Ferran Hurtado
 | last2 = Liotta | first2 = Giuseppe
 | last3 = Meijer | first3 = Henk
 | doi = 10.1016/S0925-7721(02)00129-3
 | issue = 1–2
 | journal = Computational Geometry Theory & Applications
 | pages = 35–49
 | title = Optimal and suboptimal robust algorithms for proximity graphs
 | volume = 25
 | year = 2003| doi-access = 
 | s2cid = 14573479 }}.
*{{citation
 |last=Keil 
 |first=J. Mark 
 |doi=10.1016/0925-7721(94)90014-0 
 |issue=1 
 |journal=Computational Geometry Theory & Applications 
 |pages=18–26 
 |title=Computing a subgraph of the minimum weight triangulation 
 |volume=4 
 |year=1994 
|doi-access=free 
 }}.
*{{citation
 | last1 = Kirkpatrick | first1 = David G. | author1-link = David G. Kirkpatrick
 | last2 = Radke | first2 = John D.
 | contribution = A framework for computational morphology
 | location = Amsterdam
 | pages = 217–248
 | publisher = North-Holland
 | series = Machine Intelligence and Pattern Recognition
 | title = Computational Geometry
 | volume = 2
 | year = 1985}}.
*{{citation
 | last = O'Rourke | first = Joseph | author-link = Joseph O'Rourke (professor)
 | doi = 10.1145/346048.346050
 | issue = 1
 | journal = [SIGACT News](/source/SIGACT_News)
 | pages = 28–30
 | title = Computational Geometry Column 38
 | volume = 31
 | year = 2000
 | arxiv = cs.CG/0001025}}.
*{{citation
 | last1 = Radke | first1 = John D.
 | last2 = Flodmark | first2 = Anders
 | issue = 1
 | journal = Geographic Information Sciences
 | pages = 15–23
 | title = The use of spatial decompositions for constructing street centerlines
 | url = http://www.iseis.cuhk.edu.hk/downloads/full_paper/1999-15-23.pdf
 | volume = 5
 | year = 1999| doi = 10.1080/10824009909480509
 | bibcode = 1999AnGIS...5...15R
 }}.
*{{citation
 | last = Toussaint | first = Godfried | author-link = Godfried Toussaint
 | doi = 10.1142/S0218195905001622
 | issue = 2
 | journal = International Journal of Computational Geometry and Applications
 | pages = 101–150
 | title = Geometric proximity graphs for improving nearest neighbor methods in instance-based learning and data mining
 | volume = 15
 | year = 2005}}.
*{{citation
 | last = Veltkamp | first = Remko C.
 | doi = 10.1016/0925-7721(92)90003-B
 | issue = 4
 | journal = Computational Geometry Theory & Applications
 | pages = 227–246
 | title = The γ-neighborhood graph
 | url = http://www.cs.uu.nl/groups/MG/multimedia/publications/art/cgta1992.pdf
 | volume = 1
 | year = 1992| doi-access = free
 }}.
*{{citation
 | last1 = Wang | first1 = Weizhao
 | last2 = Li | first2 = Xiang-Yang
 | last3 = Moaveninejad | first3 = Kousha
 | last4 = Wang | first4 = Yu
 | last5 = Song | first5 = Wen-Zhan
 | contribution = The spanning ratio of ''β''-skeletons
 | pages = 35–38
 | title = Proc. 15th Canadian Conference on Computational Geometry (CCCG 2003)
 | url = http://www.cccg.ca/proceedings/2003/7.pdf
 | year = 2003}}.
*{{citation
 | last1 = Zhang | first1 = Wan
 | last2 = King | first2 = Irwin
 | contribution = Locating support vectors via ''β''-skeleton technique
 | pages = 1423–1427
 | title = Proc. Proceedings of the 9th International Conference on Neural Information Processing (ICONIP'02), Orchid Country Club, Singapore, November 18-22, 2002
 | url = http://www.cs.cuhk.hk/~king/PUB/ICONIP2002-cr1968.pdf
 | year = 2002}}.
{{refend}}

Category:Euclidean plane geometry
Category:Geometric graphs
Category:Computational geometry

---
Adapted from the Wikipedia article [Beta skeleton](https://en.wikipedia.org/wiki/Beta_skeleton) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Beta_skeleton?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.