Point set triangulation

A triangulation of a set of points P in the plane is a triangulation of the convex hull of P, with all points from P being among the vertices of the triangulation. ^[1] It can alternatively be defined as a subdivision of the plane determined by a maximal set of non-crossing edges whose vertex set is P. Triangulations are special cases of planar straight-line graphs.

There are special triangulations like the Delaunay triangulation which is the geometric dual of the Voronoi diagram. Subsets of the Delaunay triangulation are the Gabriel graph, nearest neighbor graph and the minimal spanning tree.

Triangulations have a number of applications, and there is an interest to find a "good" triangulation for a given point set under some criteria. One of them is a minimum-weight triangulation. 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).^[2]

Given a set of edges that connect some pairs of the points, the problem to determine whether they contain a triangulation is NP-complete .^[3]

Triangulation and convex hull

A triangulation of the set S of n-dimensional points in general position may be derived from the convex hull of a set of points S₁ in the space of dimension larger by 1 which are the projections of the original point set onto the paraboloid surface $x_{n+1} = x_1^2+\cdots+x_n^2$. One has to construct the convex hull of the set S₁ and project it back onto the space of S. If points are not in general position, additional effort is required to triangulate the non-tetrahedral facets.

Complexity of the triangulation

Every triangulation of any set $P$ of n points has: $2n - h - 2$ triangles and $3n - h - 3$ edges where $h$ is the number of vertices of $ch(P)$ (the convex hull of P).^[4]

Algorithms

Triangle Splitting Algorithm : Find the convex hull of the point set P 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.^[5]

Incremental Algorithm : Sort the points of P according to x-coordinates. The first three points determine a triangle. Consider the next point $p$ in the ordered set and connect it with all previously considered points $\{p_1,..., p_k\}$ which are visible to p. Continue this process of adding one point of P at a time until all of P has been processed.^[6]

Time complexity of various algorithms

The following is a table of time complexity results for different kinds of optimal point set triangulations.

		minimize	maximize
minimum	angle		$O(n \log n)$ (Delaunay triangulation)
maximum		$O(n^2 \log n)$ [7] [8]
minimum	area	$O(n^2)$ [9]	$O(n^2 \log n)$ [10]
maximum		$O(n^2 \log n)$ [10]
maximum	degree	NP-complete for degree of 7 [11]
maximum	eccentricity	$O(n^3)$ [8]
minimum	edge length	$O(n \log n)$ (Closest pair of points problem)	NP-complete [12]
maximum		$O(n^2)$ [13]	$O(n \log n)$ (using the Convex hull)
sum of		NP-hard (Minimum-weight triangulation)
minimum	height		$O(n^2 \log n)$ [8]
maximum	slope	$O(n^3)$ [8]

See also

• Polygon triangulation

Notes

1. de Berg et al. 2008, Section 9.1.
2. de Berg, Mark; Otfried Cheong; Marc van Kreveld; Mark Overmars (2008). Computational Geometry: Algorithms and Applications (PDF). Springer-Verlag. ISBN 978-3-540-77973-5.
3. Lloyd 1977.
4. Edelsbrunner, Herbert; Tan, Tiow Seng; Waupotitsch, Roman (1992), "An O(n² log n) time algorithm for the minmax angle triangulation", SIAM Journal on Scientific and Statistical Computing 13 (4): 994–1008, doi:10.1137/0913058, MR 1166172.
5. Devadoss, O'Rourke Discrete and Computational Geometry. Princeton University Press, 2011, p. 60.
6. Devadoss, O'Rourke Discrete and Computational Geometry. Princeton University Press, 2011, p. 62.
7. Edelsbrunner, Tan & Waupotitsch 1990.
8. Bern et al. 1993.
9. Chazelle, Guibas & Lee 1985.
10. Vassilev 2005.
11. Jansen 1992.
12. Fekete 2012.
13. Edelsbrunner & Tan 1991.

References

• Bern, M.; Edelsbrunner, H.; Eppstein, D.; Mitchell, S.; Tan, T. S. (1993), "Edge insertion for optimal triangulations", Discrete and Computational Geometry 10 (1): 47–65, doi:10.1007/BF02573962, MR 1215322
• Chazelle, Bernard; Guibas, Leo J.; Lee, D. T. (1985). "The power of geometric duality" (PDF). BIT (BIT Computer Science and Numerical Mathematics) 25 (1): 76–90. doi:10.1007/BF01934990. ISSN 0006-3835.
• de Berg, Mark; van Kreveld, Marc; Overmars, Mark; Schwarzkopf, Otfried (2008). Computational Geometry: Algorithms and Applications (3 ed.). Springer-Verlag.
• O'Rourke, Joseph; L. Devadoss, Satyan (2011). Discrete and Computational Geometry (1 ed.). Princeton University Press.
• Edelsbrunner, Herbert; Tan, Tiow Seng; Waupotitsch, Roman (1990). An O(n2log n) time algorithm for the MinMax angle triangulation. Proceedings of the sixth annual symposium on Computational geometry. SCG '90. ACM. pp. 44–52. doi:10.1145/98524.98535. ISBN 0-89791-362-0.
• Edelsbrunner, Herbert; Tan, Tiow Seng (1991). A quadratic time algorithm for the minmax length triangulation. 32nd Annual Symposium on Foundations of Computer Science. pp. 414–423. doi:10.1109/SFCS.1991.185400. ISBN 0-8186-2445-0.
• Fekete, Sándor P. (2012). "The Complexity of MaxMin Length Triangulation". arXiv:1208.0202v1. Cite uses deprecated parameter |version= (help)
• Jansen, Klaus (1992). The Complexity of the Min-max Degree Triangulation Problem (PDF). 9th European Workshop on Computational Geometry. pp. 40–43.
• Lloyd, Errol Lynn (1977). On triangulations of a set of points in the plane. 18th Annual Symposium on Foundations of Computer Science. pp. 228–240. doi:10.1109/SFCS.1977.21. ISSN 0272-5428.
• Vassilev, Tzvetalin Simeonov (2005). Optimal Area Triangulation (PDF) (Ph.D.). University of Saskatchewan, Saskatoon.