Point-set triangulation
Template:Short description Template:Broader Template:Too technical
A triangulation of a set of points <math>\mathcal{P}</math> in the Euclidean space <math>\mathbb{R}^d</math> is a simplicial complex that covers the convex hull of <math>\mathcal{P}</math>, and whose vertices belong to <math>\mathcal{P}</math>.<ref name="DRS">Template:Cite book</ref> In the plane (when <math>\mathcal{P}</math> is a set of points in <math>\mathbb{R}^2</math>), triangulations are made up of triangles, together with their edges and vertices. Some authors require that all the points of <math>\mathcal{P}</math> are vertices of its triangulations.Template:Sfn In this case, a triangulation of a set of points <math>\mathcal{P}</math> in the plane can alternatively be defined as a maximal set of non-crossing edges between points of <math>\mathcal{P}</math>. 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 <math>\mathcal{P}</math> in the plane contains the Gabriel graph, the nearest neighbor graph and the minimal spanning tree of <math>\mathcal{P}</math>.
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).<ref name="deBerg">Template:Cite book</ref>
Given a set of edges that connect points of the plane, the problem to determine whether they contain a triangulation is NP-complete.Template:Sfn
Regular triangulationsEdit
Some triangulations of a set of points <math>\mathcal{P}\subset\mathbb{R}^d</math> can be obtained by lifting the points of <math>\mathcal{P}</math> into <math>\mathbb{R}^{d+1}</math> (which amounts to add a coordinate <math>x_{d+1}</math> to each point of <math>\mathcal{P}</math>), by computing the convex hull of the lifted set of points, and by projecting the lower faces of this convex hull back on <math>\mathbb{R}^d</math>. The triangulations built this way are referred to as the regular triangulations of <math>\mathcal{P}</math>. When the points are lifted to the paraboloid of equation <math>x_{d+1} = x_1^2+\cdots+x_d^2</math>, this construction results in the Delaunay triangulation of <math>\mathcal{P}</math>. 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. In the case of Delaunay triangulations, this amounts to require that no <math>d+2</math> points of <math>\mathcal{P}</math> lie in the same sphere.
Combinatorics in the planeEdit
Every triangulation of any set <math>\mathcal{P}</math> of <math>n</math> points in the plane has <math> 2n - h - 2</math> triangles and <math>3n - h - 3</math> edges where <math>h</math> is the number of points of <math>\mathcal{P}</math> in the boundary of the convex hull of <math>\mathcal{P}</math>. This follows from a straightforward Euler characteristic argument.<ref>Template:Citation.</ref>
Algorithms to build triangulations in the planeEdit
Triangle Splitting Algorithm : Find the convex hull of the point set <math>\mathcal{P}</math> 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.<ref>Devadoss, O'Rourke Discrete and Computational Geometry. Princeton University Press, 2011, p. 60.</ref>
Incremental Algorithm : Sort the points of <math>\mathcal{P}</math> according to x-coordinates. The first three points determine a triangle. Consider the next point <math>p</math> in the ordered set and connect it with all previously considered points <math>\{p_1,..., p_k\}</math> which are visible to p. Continue this process of adding one point of <math>\mathcal{P}</math> at a time until all of <math>\mathcal{P}</math> has been processed.<ref>Devadoss, O'Rourke Discrete and Computational Geometry. Princeton University Press, 2011, p. 62.</ref>
Time complexity of various algorithmsEdit
The following table reports time complexity results for the construction of triangulations of point sets in the plane, under different optimality criteria, where <math>n</math> is the number of points.
| minimize | maximize | ||
|---|---|---|---|
| minimum | angle | <math>O(n \log n)</math> (Delaunay triangulation) | |
| maximum | <math>O(n^2 \log n)</math> Template:Sfn Template:Sfn | ||
| minimum | area | <math>O(n^2)</math> Template:Sfn | <math>O(n^2 \log n)</math> Template:Sfn |
| maximum | <math>O(n^2 \log n)</math> Template:Sfn | ||
| maximum | degree | NP-complete for degree of 7 Template:Sfn |
|
| maximum | eccentricity | <math>O(n^3)</math> Template:Sfn | |
| minimum | edge length | <math>O(n \log n)</math> (Closest pair of points problem) |
NP-complete Template:Sfn |
| maximum | <math>O(n^2)</math> Template:Sfn | <math>O(n \log n)</math> (using the Convex hull) | |
| sum of | NP-hard (Minimum-weight triangulation) |
||
| minimum | height | <math>O(n^2 \log n)</math> Template:Sfn | |
| maximum | slope | <math>O(n^3)</math> Template:Sfn | |