 DelaunayGraph - Maple Help

GraphTheory[GeometricGraphs]

 DelaunayGraph
 construct Delaunay graph Calling Sequence DelaunayGraph(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 DelaunayGraph(P, opts) command returns a Delaunay 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.
 • A Delaunay graph is a undirected graph corresponding to a Delaunay triangulation on P. Its vertices correspond to the points in $P$ and an edge exists between points $p$ and $q$ from $P$ whenever $p$ and $q$ form the corners of a triangle in a Delaunay triangulation.
 • The Delaunay graph is an example of geometric spanner, a graph for which the weighted graph distance connecting any two vertices $p$ and $q$ is a bounded multiple of the Euclidean distance between $p$ and $q$.
 • 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 the Delaunay 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}\left[8\right]\right)$
 ${\mathrm{points}}{≔}\begin{array}{c}\left[\begin{array}{cc}{9.85017697341803}& {82.9750304386195}\\ {86.0670183749663}& {83.3188659363996}\\ {64.3746795546741}& {73.8671607639673}\\ {57.3670557294666}& {2.34399775883031}\\ {23.6234264844933}& {52.6873367387328}\\ {47.0027547350003}& {22.2459488367552}\\ {74.9213491558963}& {62.0471820220718}\\ {92.1513434709073}& {96.3107262637080}\\ {48.2319624355944}& {63.7563267144141}\\ {90.9441877431805}& {33.8527464913022}\\ {⋮}& {⋮}\end{array}\right]\\ \hfill {\text{60 × 2 Matrix}}\end{array}$ (1)
 > $\mathrm{DG}≔\mathrm{DelaunayGraph}\left(\mathrm{points}\right)$
 ${\mathrm{DG}}{≔}{\mathrm{Graph 1: an undirected unweighted graph with 60 vertices and 167 edge\left(s\right)}}$ (2)
 > $\mathrm{DrawGraph}\left(\mathrm{DG}\right)$  References

 Chew, L. Paul (1986), "There is a planar graph almost as good as the complete graph", Proc. 2nd Annual Symposium on Computational Geometry, pp. 169–177. doi:10.1145/10515.10534 Compatibility

 • The GraphTheory[GeometricGraphs][DelaunayGraph] command was introduced in Maple 2020.