Point-set triangulation
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]
Regular triangulations
[edit]Some triangulations of a set of points can be obtained by lifting the points of into (which amounts to add a coordinate to each point of ), by computing the convex hull of the lifted set of points, and by projecting the lower faces of this convex hull back on . The triangulations built this way are referred to as the regular triangulations of . When the points are lifted to the paraboloid of equation , this construction results in the Delaunay triangulation of . 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 points of lie in the same sphere.
Combinatorics in the plane
[edit]Every triangulation of any set of points in the plane has triangles and edges where is the number of points of in the boundary of the convex hull of . This follows from a straightforward Euler characteristic argument.[5]
Algorithms to build triangulations in the plane
[edit]Triangle Splitting Algorithm : Find the convex hull of the point set 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 according to x-coordinates. The first three points determine a triangle. Consider the next point in the ordered set and connect it with all previously considered points which are visible to p. Continue this process of adding one point of at a time until all of has been processed.[7]
Time complexity of various algorithms
[edit]The following table reports time complexity results for the construction of triangulations of point sets in the plane, under different optimality criteria, where is the number of points.
minimize | maximize | ||
---|---|---|---|
minimum | angle | (Delaunay triangulation) | |
maximum | [8] [9] | ||
minimum | area | [10] | [11] |
maximum | [11] | ||
maximum | degree | NP-complete for degree of 7 [12] |
|
maximum | eccentricity | [9] | |
minimum | edge length | (Closest pair of points problem) |
NP-complete [13] |
maximum | [14] | (using the Convex hull) | |
sum of | NP-hard (Minimum-weight triangulation) |
||
minimum | height | [9] | |
maximum | slope | [9] |
See also
[edit]Notes
[edit]- ^ De Loera, Jesús A.; Rambau, Jörg; Santos, Francisco (2010). Triangulations, Structures for Algorithms and Applications. Algorithms and Computation in Mathematics. Vol. 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(n2 log n) time algorithm for the minmax angle triangulation", SIAM Journal on Scientific and Statistical Computing, 13 (4): 994–1008, CiteSeerX 10.1.1.66.2895, 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.
- ^ a b c d Bern et al. 1993.
- ^ Chazelle, Guibas & Lee 1985.
- ^ a b Vassilev 2005.
- ^ Jansen 1992.
- ^ Fekete 2012.
- ^ Edelsbrunner & Tan 1991.
References
[edit]- 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. 25 (1). BIT Computer Science and Numerical Mathematics: 76–90. doi:10.1007/BF01934990. ISSN 0006-3835. S2CID 122411548.
- 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. CiteSeerX 10.1.1.66.2895. 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. CiteSeerX 10.1.1.66.8959. 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 [cs.CG].
- 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. Switching and Automata Theory, 1974., IEEE Conference Record of 15th Annual Symposium on. 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. Archived from the original (PDF) on 2017-08-13. Retrieved 2013-06-15.