construct Delaunay graph
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 = 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.
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.
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.
Generate a set of random two-dimensional points and draw the Delaunay graph.
points ≔ LinearAlgebra:-RandomMatrix⁡60,2,generator=0..100.,datatype=float8
DG ≔ DelaunayGraph⁡points
DG≔Graph 1: an undirected graph with 60 vertices and 167 edge(s)
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
The GraphTheory[GeometricGraphs][DelaunayGraph] command was introduced in Maple 2020.
For more information on Maple 2020 changes, see Updates in Maple 2020.
Download Help Document