## Delaunay TriangulationsA If all points of
## Properties of Delaunay Triangulations- A Delaunay triangulation maximizes the smallest interior angle of any triangle.
- Delaunay triangulations tend to "rounder" triangles than other triangulations. This property is desirable for numerical applications.
- Delaunay triangulations are useful in many contexts.
- The Delaunay triangulation of a set of points is in general not unique.
## RepresentationThe triangulation is represented by the parameterized graph`GRAPH<POINT,int> G` . `G` is a straight
line embedded plane map. It corresponds to the triangulation `T`
of the set of points `L` as follows:
- Nodes are in one-to-one correspondence with the points in
`L` `G` is bidirected- For each node
`v` of`G` the list`A(v)` of edges out of`v` is ordered cyclically. This cyclic ordering agrees with the counter-clockwise ordering of the edges incident to the point in`T` corresponding to`v` . - Each edge
`e` of`G` has an integer label that gives information about the edge.`G[e]=2` if`e` is on the convex hull of`L` `G[e]=0` if`e` is on the Delaunay Diagram of`L` `G[e]=1` otherwise
## Running TimeThe running time of the algorithms is ## Verifying Delaunay TriangulationsThe functionbool Is_Delaunay_Triangulation(const GRAPH<POINT,int>& G, delaunay_voronoi_kind kind) checks whether We use the notation ## Algorithms for Constrained Delaunay TriangulationsLEDA provides additional algorithms for computing Delaunay triangulations of segments, plane maps. Details can be found on the Manual Page of Geometry Algorithms. |
## See also:
## Manual Entries |

Please send any suggestions, comments or questions to leda@algorithmic-solutions.com

© Copyright 2001-2003, Algorithmic Solutions Software GmbH