## TriangulationsA
## 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 algorithm is an extension of the sweep algorithm for convex hull. The running time is`O(nlogn)` .
## Verifying TriangulationsThe functionbool Is_Triangulation(GRAPH<POINT,int>& G) returns `POINT` to indicate that the algorithm works both for
`points` and `rat_points` . See also Writing
Kernel Independent Code.
## Algorithms for Constrained TriangulationsLEDA provides additional algorithms for computing triangulations of segments, plane maps, and polygons. 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