GraphTheory[GeometricGraphs] - Maple Programming Help

# Online Help

###### All Products    Maple    MapleSim

Home : Support : Online Help : Mathematics : Discrete Mathematics : Graph Theory : GraphTheory Package : GeometricGraphs : GraphTheory/GeometricGraphs/RelativeNeighborhoodGraph

GraphTheory[GeometricGraphs]

 RelativeNeighborhoodGraph
 construct a relative neighbor graph

 Calling Sequence RelativeNeighborhoodGraph( 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 : true or false
 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 RelativeNeighborhoodGraph(P,opts) command returns a relative neighbor graph for the point set P.
 • The parameter P must be a Matrix or list of lists representing a set of points.

Definition

 • 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 relative neighborhood graph is the undirected graph whose vertices correspond to the points in $P$ and in which vertices $p$ and $q$ share an edge if there does not exist any $r\in P$ such that $\mathrm{dist}\left(p,r\right)<\mathrm{dist}\left(p,q\right)$ and $\mathrm{dist}\left(q,r\right)<\mathrm{dist}\left(p,q\right)$.
 • It has the following relationships with other graphs:
 The Euclidean minimum spanning tree on P is a subgraph of the relative neighborhood graph on P.
 The relative neighborhood graph on P is a subgraph of the Gabriel graph on P.

Examples

Generate a set of random two-dimensional points.

 > $\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}\left[8\right]\right)$
  (1)
 > $\mathrm{RNG}≔\mathrm{RelativeNeighborhoodGraph}\left(\mathrm{points}\right)$
 ${\mathrm{RNG}}{≔}{\mathrm{Graph 1: an undirected unweighted graph with 60 vertices and 65 edge\left(s\right)}}$ (2)
 > $\mathrm{DrawGraph}\left(\mathrm{RNG}\right)$

References

 Supowit, K. J. (1983), "The relative neighborhood graph, with an application to minimum spanning trees", J. ACM, 30 (3): 428–448, doi:10.1145/2402.322386.

Compatibility

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

 See Also