Graphics Reference
In-Depth Information
Figure
.
.
Relative neighborhood graph
Figure
.
.
Minimum spanning tree
In a Gabriel graph, an edge exists between any pair of points that have a D
con-
taining no points.
In a relative neighborhood graph, an edge exists between any pair of points p and
q for which r is the distance between p and q and the intersection of D
(
p, r
)
and
D
contains no points. his intersection region is called a lune.
A beta skeleton graph isacompromisebetween the Gabriel andrelative neighbor-
hoodgraphs.Itusesalunewhosesizeisdeterminedbyaparameterβ.Ifβ
(
q, r
)
=
,
the beta skeleton graph is a Gabriel graph. If β
=
, the beta skeleton graph is
a relative neighborhood graph.
A minimum spanning tree is an acyclical subset of a Gabriel graph.