A triangulation of a set of points in the Euclidean space is a simplicial complex that covers the convex hull. In the plane are vertices of its triangulations.. In the plane, triangulations are special cases of planar straight-line graphs.

The Delaunay triangulations are the geometric duals of Voronoi diagrams in the plane contains the Gabriel graph, the nearest neighbor graph and the minimal spanning tree.

Triangulations have a number of applications, and there is an interest to find the "good" triangulations of a given point set under some criteria as, for instance minimum-weight triangulations. Sometimes it is desirable to have a triangulation with special properties, e.g., in which all triangles have large angles (long and narrow ("splinter") triangles are avoided).

Given a set of edges that connect points of the plane, the problem to determine whether they contain a triangulation is NP-complete.

Regular triangulations

, this construction results in the Delaunay triangulation. Note that, in order for this construction to provide a triangulation, the lower convex hull of the lifted set of points needs to be simplicial lie in the same sphere.

Variants and extensions

In addition to classical Delaunay and regular triangulations, several other forms and problems related to point-set triangulations have been studied in computational geometry. The minimum-weight triangulation (MWT) seeks a triangulation of a point set that minimizes the total edge length; although this problem was shown to be NP-hard, approximation algorithms and heuristics have been developed. A related heuristic, the greedy triangulation, constructs a triangulation by repeatedly adding the shortest edge that does not intersect existing edges, yielding good approximations in practice. Another special type is the Pitteway triangulation, in which each edge connects a pair of points whose Voronoi cells share a boundary segment; such triangulations are closely related to the Delaunay and Gabriel graphs. Point-set triangulations can also be viewed as maximal planar straight-line graphs, since no additional straight edges can be added without destroying planarity. More recently, machine learning approaches have been proposed to generate triangulations directly from unstructured point clouds, such as PointTriNet, which uses neural networks to learn triangulation patterns for 2D and 3D data. Advances in combinatorial geometry have also yielded new bounds on the number of distinct triangulations realizable on a fixed point set, highlighting the exponential complexity of these structures.

Combinatorics in the plane

in the boundary of the convex hull. This follows from a straightforward Euler characteristic argument.

Algorithms to build triangulations in the plane

Triangle Splitting Algorithm and triangulate this hull as a polygon. Choose an interior point and draw edges to the three vertices of the triangle that contains it. Continue this process until all interior points are exhausted.

Incremental Algorithm which are visible to p. has been processed.

Time complexity of various algorithms

is the number of points.

See also

• Mesh generation

• Polygon triangulation

Notes

References

de:Gitter (Geometrie)#Dreiecksgitter