GabrielGraph - Maple Help
For the best experience, we recommend viewing online help using Google Chrome or Microsoft Edge.

Online Help

All Products    Maple    MapleSim

GraphTheory[GeometricGraphs]

 GabrielGraph
 construct Gabriel graph

 Calling Sequence GabrielGraph( P, opts )

Parameters

 P - Matrix or list of lists representing set of points opts - (optional) one or more options as specified below

Options

 • triangulation = list of three-element lists
 Supply a previously computed Delaunay triangulation of P. The input must be a valid Delaunay triangulation in the format returned by ComputationalGeometry[DelaunayTriangulation]: a list of three-element lists of integers, representing triangles in a triangulation of P.
 • vertices = list of integers, strings or symbols
 Specifies the vertices to be used in the generated graph.
 • weighted = truefalse
 If weighted=true, the result is a weighted graph whose edge weights correspond to the Euclidean distance between points. The default is false.

Description

 • The GabrielGraph(P, opts) command returns the Gabriel graph for the point set P.
 • The parameter P must be a Matrix or list of lists representing a set of points.

Definitions

 • Let $P$ be a set of points in $n$ dimensions, let $p$ and $q$ be arbitrary points from $P$, and let $\mathrm{dist}\left(p,q\right)$ be the Euclidean distance between $p$ and $q$.
 • The Gabriel graph the graph whose vertices correspond to points in $P$ and whose edges consist of those pairs $p$ and $q$ from $P$ for which the closed ball centered halfway between $p$ and $q$ with diameter equal to $\mathrm{dist}\left(p-q\right)$ contains no other points from $P$.
 Formally, define the ball $B\left(p,q\right)$ to be those points $r\in P$ such that $\mathrm{dist}\left(r,\frac{p}{2}+\frac{q}{2}\right)\le \frac{\mathrm{dist}\left(p,q\right)}{2}$. The Gabriel graph has an edge between $p$ and $q$ if and only if $B\left(p,q\right)=\varnothing$.
 • The Gabriel graph has the following relationships with other graphs:
 The Euclidean minimum spanning tree on P is a subgraph of the Gabriel graph on P.
 The nearest neighbor graph on P is a subgraph of the Gabriel graph on P.
 The relative neighborhood graph on P is a subgraph of the Gabriel graph on P.
 The Urquhart graph on P is a subgraph of the Gabriel graph on P.
 The Gabriel graph on P is a subgraph of the Delaunay graph on P.

Examples

Generate a set of random two-dimensional points and draw a Gabriel graph.

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$
 > $\mathrm{with}\left(\mathrm{GeometricGraphs}\right):$
 > $\mathrm{points}≔\mathrm{LinearAlgebra}:-\mathrm{RandomMatrix}\left(60,2,\mathrm{generator}=0..100.,\mathrm{datatype}={\mathrm{float}}_{8}\right)$
 > $\mathrm{GG}≔\mathrm{GabrielGraph}\left(\mathrm{points}\right)$
 ${\mathrm{GG}}{≔}{\mathrm{Graph 1: an undirected graph with 60 vertices and 105 edge\left(s\right)}}$ (1)
 > $\mathrm{DrawGraph}\left(\mathrm{GG}\right)$

References

 Gabriel, Kuno Ruben; Sokal, Robert Reuven (1969), "A new statistical approach to geographic variation analysis", Systematic Biology, Society of Systematic Biologists, 18(3): 259–278. doi:10.2307/2412323.

Compatibility

 • The GraphTheory[GeometricGraphs][GabrielGraph] command was introduced in Maple 2020.
 • For more information on Maple 2020 changes, see Updates in Maple 2020.

 See Also