
In
computational geometry and
geometric graph theory
Geometric graph theory in the broader sense is a large and amorphous subfield of graph theory, concerned with graphs defined by geometric means. In a stricter sense, geometric graph theory studies combinatorial and geometric properties of geomet ...
, a ''β''-skeleton or beta skeleton is an
undirected graph
In discrete mathematics, particularly in graph theory, a graph is a structure consisting of a set of objects where some pairs of the objects are in some sense "related". The objects are represented by abstractions called '' vertices'' (also call ...
defined from a set of points in the
Euclidean plane
In mathematics, a Euclidean plane is a Euclidean space of Two-dimensional space, dimension two, denoted \textbf^2 or \mathbb^2. It is a geometric space in which two real numbers are required to determine the position (geometry), position of eac ...
. 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

Let ''β'' be a positive
real number
In mathematics, a real number is a number that can be used to measure a continuous one- dimensional quantity such as a duration or temperature. Here, ''continuous'' means that pairs of values can have arbitrarily small differences. Every re ...
, and calculate an angle ''θ'' using the formulas
:
For any two points ''p'' and ''q'' in the plane, let ''R''
''pq'' be the set of points for which angle ''prq'' is greater than ''θ''. Then ''R''
''pq'' takes the form of a union of two open disks with diameter ''βd''(''p'',''q'') for ''β'' ≥ 1 and ''θ'' ≤ π/2, and it takes the form of the intersection of two open disks with diameter ''d''(''p'',''q'')/''β'' for ''β'' ≤ 1 and ''θ'' ≥ π/2. When ''β'' = 1 the two formulas give the same value ''θ'' = π/2, and ''R''
''pq'' takes the form of a single open disk with ''pq'' as its diameter.
The ''β''-skeleton of a
discrete set
In mathematics, a point (topology), point is called an isolated point of a subset (in a topological space ) if is an element of and there exists a Neighborhood (mathematics), neighborhood of that does not contain any other points of . This i ...
''S'' of points in the plane is the
undirected graph
In discrete mathematics, particularly in graph theory, a graph is a structure consisting of a set of objects where some pairs of the objects are in some sense "related". The objects are represented by abstractions called '' vertices'' (also call ...
that connects two points ''p'' and ''q'' with an edge ''pq'' whenever ''R''
''pq'' contains no points of ''S''. That is, the ''β''-skeleton is the empty region graph defined by the regions ''R''
''pq''.
[.] 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''
''pq'' for ''β'' > 1 are not unions of two disks but rather
lenses
A lens is a transmissive optical device that focuses or disperses a light beam by means of refraction. A simple lens consists of a single piece of transparent material, while a compound lens consists of several simple lenses (''elements''), ...
(more often called in this context "
lunes"), 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''
''pq'' is empty of other input points. For this alternative definition, the
relative neighborhood graph is a special case of a ''β''-skeleton with ''β'' = 2. The two definitions coincide for ''β'' ≤ 1, and for larger values of ''β'' the circle-based skeleton is a
subgraph 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
In the mathematical field of graph theory, the term "null graph" may refer either to the order-zero graph, or alternatively, to any edgeless graph (the latter is sometimes called an "empty graph").
Order-zero graph
The order-zero graph, , is t ...
. 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 as a
scale-invariant variation of the
alpha shapes of . 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
In shape analysis, skeleton (or topological skeleton) of a shape is a thin version of that shape that is equidistant to its boundaries. The skeleton usually emphasizes geometrical and topological properties of the shape, such as its connectivit ...
describes the shape of a two-dimensional region. Several generalizations of the ''β''-skeleton to graphs defined by other empty regions have also been considered.
Properties
If ''β'' varies continuously from 0 to ∞, the circle-based ''β''-skeletons form a sequence of graphs extending from the
complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices i ...
to the
empty graph
In the mathematical field of graph theory, the term "null graph" may refer either to the order-zero graph, or alternatively, to any edgeless graph (the latter is sometimes called an "empty graph").
Order-zero graph
The order-zero graph, , is t ...
. The special case ''β'' = 1 leads to the
Gabriel graph, which is known to contain the
Euclidean minimum spanning tree; therefore, the ''β''-skeleton also contains the Gabriel graph and the minimum spanning tree whenever ''β'' ≤ 1.
For any constant ''β'', a
fractal
In mathematics, a fractal is a Shape, geometric shape containing detailed structure at arbitrarily small scales, usually having a fractal dimension strictly exceeding the topological dimension. Many fractals appear similar at various scale ...
construction resembling a flattened version of the
Koch snowflake
The Koch snowflake (also known as the Koch curve, Koch star, or Koch island) is a fractal curve and one of the earliest fractals to have been described. It is based on the Koch curve, which appeared in a 1904 paper titled "On a Continuous Cur ...
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
In computational geometry, a Delaunay triangulation or Delone triangulation of a set of points in the plane subdivides their convex hull into triangles whose circumcircles do not contain any of the points; that is, each circumcircle has its gen ...
, ''β''-skeletons have unbounded
stretch factor
The stretch factor (i.e., Lipschitz continuity#Definition, bilipschitz constant) of an embedding measures the factor by which the embedding distorts distances. Suppose that one metric space is embedded into another metric space by a metric map ...
and are not
geometric spanner
A geometric spanner or a -spanner graph or a -spanner was initially introduced as a weighted graph over a set of points as its vertices for which there is a -path between any pair of vertices for a fixed parameter . A -path is defined as a path ...
s.
Algorithms
A
naïve algorithm that tests each triple ''p'', ''q'', and ''r'' for membership of ''r'' in the region ''R''
''pq'' can construct the ''β''-skeleton of any set of ''n'' points in time O(''n''
3).
When ''β'' ≥ 1, the ''β''-skeleton (with either definition) is a subgraph of the Gabriel graph, which is a subgraph of the
Delaunay triangulation
In computational geometry, a Delaunay triangulation or Delone triangulation of a set of points in the plane subdivides their convex hull into triangles whose circumcircles do not contain any of the points; that is, each circumcircle has its gen ...
. 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'' log ''n'') by computing the Delaunay triangulation and using this test to filter its edges.
[.]
For ''β'' < 1, a different algorithm of allows the construction of the ''β''-skeleton in time O(''n''
2). 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
In Euclidean geometry, a regular polygon is a polygon that is Equiangular polygon, direct equiangular (all angles are equal in measure) and Equilateral polygon, equilateral (all sides have the same length). Regular polygons may be either ''convex ...
) for which the ''β''-skeleton is a
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
Image analysis or imagery analysis is the extraction of meaningful information from images; mainly from digital images by means of digital image processing techniques. Image analysis tasks can be as simple as reading barcode, bar coded tags or a ...
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 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 ''β'' = 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
In mathematics, curvature is any of several strongly related concepts in geometry that intuitively measure the amount by which a curve deviates from being a straight line or by which a surface deviates from being a plane. If a curve or su ...
of the surface. However in experimental testing a lower value, ''β'' = 1.2, was more effective for reconstructing street maps from sets of points marking the center lines of streets in a
geographic information system
A geographic information system (GIS) consists of integrated computer hardware and Geographic information system software, software that store, manage, Spatial analysis, analyze, edit, output, and Cartographic design, visualize Geographic data ...
. For generalizations of the ''β''-skeleton technique to reconstruction of surfaces in three dimensions, see .
Circle-based ''β''-skeletons have been used to find subgraphs of the
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
In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements (nodes or edges) that need to be removed to separate the remaining nodes into two or more isolated subgrap ...
on all of the input points, then the remaining minimum weight triangulation edges may be found in
polynomial time
In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations p ...
by
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.
''β''-skeletons have also been applied in
machine learning
Machine learning (ML) is a field of study in artificial intelligence concerned with the development and study of Computational statistics, statistical algorithms that can learn from data and generalise to unseen data, and thus perform Task ( ...
to solve geometric
classification
Classification is the activity of assigning objects to some pre-existing classes or categories. This is distinct from the task of establishing the classes themselves (for example through cluster analysis). Examples include diagnostic tests, identif ...
problems and in
wireless ad hoc network
A wireless ad hoc network (WANET) or mobile ad hoc network (MANET) is a decentralized type of wireless network. The network is ad hoc because it does not rely on a pre-existing infrastructure, such as routers or wireless access points. Instead, ...
s as a mechanism for controlling communication complexity by choosing a subset of the pairs of wireless stations that can communicate with each other.
[.]
Notes
References
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
{{refend
Euclidean plane geometry
Geometric graphs
Computational geometry