Algorithmic Solutions > LEDA > LEDA Guide > Geometry Algorithms > Triangulations

## Triangulations

A triangulation of a set `S` of points is a partition of the convex hull of `S` into triangles. This assumes that not all points of `S` are collinear.

### Strengths

• point location queries
• nearest neighbor queries
• range queries
• interpolation

On the right you see a triangulation of a set of points in the plane, the points and edges on the convex hull are drawn in red. The picture is a screenshot from the example of computing and verifying a triangulation.

### Representation

The 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 Time

The algorithm is an extension of the sweep algorithm for convex hull. The running time is `O(nlogn)`.

### Verifying Triangulations

The function
`    bool Is_Triangulation(GRAPH<POINT,int>& G)`

returns `true` if `G` is a convex planar subdivision in which every bounded face is a triangle or all nodes of `G` lie on a common line. See also Verification of Geometric Structures.

We use the notation `POINT` to indicate that the algorithm works both for `points` and `rat_points`. See also Writing Kernel Independent Code.

### Algorithms for Constrained Triangulations

LEDA provides additional algorithms for computing triangulations of segments, plane maps, and polygons. Details can be found on the Manual Page of Geometry Algorithms.

Data Types for 2-D Geometry

Convex Hulls

Linear Lists

Parameterized Graphs

Delaunay Triangulations

Delaunay Diagrams

Verification of Geometric Structures

Geometry Algorithms

Geometry

GeoWin

### Manual Entries

Manual Page of Geometry Algorithms