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≔9.8501769734180382.975030438619586.067018374966383.318865936399664.374679554674173.867160763967357.36705572946662.3439977588303123.623426484493352.687336738732847.002754735000322.245948836755274.921349155896362.047182022071892.151343470907396.310726263708048.231962435594463.756326714414190.944187743180533.8527464913022⋮⋮60 × 2 Matrix
DG≔Graph 1: an undirected unweighted 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
What kind of issue would you like to report? (Optional)