construct a relative neighbor graph
RelativeNeighborhoodGraph( P, opts )
Matrix or list of lists representing set of points
(optional) one or more options as specified below
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.
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.
Let P be a set of points in n dimensions, let p and q be arbitrary points from P, and let dist⁡p,q 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∈P such that dist⁡p,r<dist⁡p,q and dist⁡q,r<dist⁡p,q.
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.
Generate a set of random two-dimensional points.
points ≔ LinearAlgebra:-RandomMatrix⁡60,2,generator=0..100.,datatype=float8
RNG ≔ RelativeNeighborhoodGraph⁡points
RNG≔Graph 1: an undirected graph with 60 vertices and 65 edge(s)
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.
The GraphTheory[GeometricGraphs][RelativeNeighborhoodGraph] command was introduced in Maple 2020.
For more information on Maple 2020 changes, see Updates in Maple 2020.
Download Help Document