Algorithmic Solutions > LEDA > LEDA Guide > Geometry Algorithms > 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.


  • 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.

Example of Triangulations

Example of computing and verifying a triangulation


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.

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.

See also:

Data Types for 2-D Geometry

Convex Hulls

Linear Lists

Parameterized Graphs

Writing Kernel Independent Code

Delaunay Triangulations

Delaunay Diagrams

Verification of Geometric Structures

Geometry Algorithms




Manual Entries

Manual Page of Geometry Algorithms

Please send any suggestions, comments or questions to
© Copyright 2001-2003, Algorithmic Solutions Software GmbH