Point set triangulation

Two different triangulations of the same set of 9 points in the plane.

A triangulation of a set of points ${\mathcal {P}}$ in the Euclidean space $\mathbb {R} ^{d}$ is a simplicial complex that covers the convex hull of ${\mathcal {P}}$ , and whose vertices belong to ${\mathcal {P}}$ .^[1] In the plane (when ${\mathcal {P}}$ is a set of points in $\mathbb {R} ^{2}$ ), triangulations are made up of triangles, together with their edges and vertices. Some authors require that all the points of ${\mathcal {P}}$ are vertices of its triangulations.^[2] In this case, a triangulation of a set of points ${\mathcal {P}}$ in the plane can alternatively be defined as a maximal set of non-crossing edges between points of ${\mathcal {P}}$ . 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 ${\mathcal {P}}$ in the plane contains the Gabriel graph, the nearest neighbor graph and the minimal spanning tree of ${\mathcal {P}}$ .

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]

Regular triangulations

Some triangulations of a set of points ${\mathcal {P}}\subset \mathbb {R} ^{d}$ can be obtained by lifting the points of ${\mathcal {P}}$ into ${\mathbb {R}}^{{d+1}}$ (which amounts to add a coordinate $x_{d+1}$ to each point of ${\mathcal {P}}$ ), by computing the convex hull of the lifted set of points, and by projecting the lower faces of this convex hull back on $\mathbb {R} ^{d}$ . The triangulations built this way are referred to as the regular triangulations of ${\mathcal {P}}$ . When the points are lifted to the paraboloid of equation $x_{d+1}=x_{1}^{2}+\cdots +x_{d}^{2}$ , this construction results in the Delaunay triangulation of ${\mathcal {P}}$ . 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 $d+2$ points of ${\mathcal {P}}$ lie in the same sphere.

Combinatorics in the plane

Every triangulation of any set ${\mathcal {P}}$ of $n$ points in the plane has $2n - h - 2$ triangles and $3n - h - 3$ edges where $h$ is the number of points of ${\mathcal {P}}$ in the boundary of the convex hull of ${\mathcal {P}}$ . This follows from a straightforward Euler characteristic argument.^[5]

Algorithms to build triangulations in the plane

Triangle Splitting Algorithm : Find the convex hull of the point set ${\mathcal {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.^[6]

Incremental Algorithm : Sort the points of ${\mathcal {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 ${\mathcal {P}}$ at a time until all of ${\mathcal {P}}$ has been processed.^[7]

Time complexity of various algorithms

The following table reports time complexity results for the construction of triangulations of point sets in the plane, under different optimality criteria, where $n$ is the number of points.

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

Notes

↑ De Loera, Jesús A.; Rambau, Jörg; Santos, Francisco (2010). Triangulations, Structures for Algorithms and Applications. Algorithms and Computation in Mathematics. 25. Springer.
↑ de Berg et al. 2008, Section 9.1.
↑ 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.
↑ Lloyd 1977.
↑ 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 .
↑ Devadoss, O'Rourke Discrete and Computational Geometry. Princeton University Press, 2011, p. 60.
↑ Devadoss, O'Rourke Discrete and Computational Geometry. Princeton University Press, 2011, p. 62.
↑ Edelsbrunner, Tan & Waupotitsch 1990.
1 2 3 4 Bern et al. 1993.
↑ Chazelle, Guibas & Lee 1985.
1 2 Vassilev 2005.
↑ Jansen 1992.
↑ Fekete 2012.
↑ 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.
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.

This article is issued from Wikipedia - version of the 10/21/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.