This article may be too technical for most readers to understand.(June 2021) |
A triangulation of a set of points in the Euclidean space is a simplicial complex that covers the convex hull of , and whose vertices belong to .[1] In the plane (when is a set of points in ), triangulations are made up of triangles, together with their edges and vertices. Some authors require that all the points of are vertices of its triangulations.[2] In this case, a triangulation of a set of points in the plane can alternatively be defined as a maximal set of non-crossing edges between points of . In the plane, triangulations are special cases of planar straight-line graphs.
A particularly interesting kind of triangulations are the Delaunay triangulations. They are the geometric duals of Voronoi diagrams. The Delaunay triangulation of a set of points in the plane contains the Gabriel graph, the nearest neighbor graph and the minimal spanning tree of .
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).[3]
Given a set of edges that connect points of the plane, the problem to determine whether they contain a triangulation is NP-complete.[4]