{{Short description|Simplicial complex in Euclidean geometry}} {{broader|Triangulation (geometry)}} {{Too technical|date=June 2021}} Two different triangulations of the same set of 9 points in the plane.|thumb 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">{{cite book | last1 = De Loera | first1 = Jesús A. | author-link1 = Jesús A. De Loera | last2 = Rambau | first2 = Jörg | last3 = Santos | first3 = Francisco | author-link3 = Francisco Santos Leal | year = 2010 | title = Triangulations, Structures for Algorithms and Applications | series = Algorithms and Computation in Mathematics | volume = 25 | publisher = Springer}}</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.{{sfn |de Berg|van Kreveld|Overmars|Schwarzkopf|2008|loc=Section 9.1}}<ref>{{Citation |last1=Agryzkov |first1=Taras |title=A Method to Triangulate a Set of Points in the Plane |date=2014 |work=Computational Science and Its Applications – ICCSA 2014 |volume=8580 |pages=330–341 |editor-last=Murgante |editor-first=Beniamino |url=http://link.springer.com/10.1007/978-3-319-09129-7_25 |access-date=2025-08-19 |place=Cham |publisher=Springer International Publishing |doi=10.1007/978-3-319-09129-7_25 |isbn=978-3-319-09128-0 |last2=Oliver |first2=José L. |last3=Tortosa |first3=Leandro |last4=Vicent |first4=José F. |editor2-last=Misra |editor2-first=Sanjay |editor3-last=Rocha |editor3-first=Ana Maria A. C. |editor4-last=Torre |editor4-first=Carmelo|url-access=subscription }}</ref> 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.<ref>{{cite arXiv |last=Bui |first=Hong Duc |title=On existence of a compatible triangulation with the double circle order type |date=2025 |class=math.CO |eprint=2508.04602}}</ref>
The Delaunay triangulations<ref>{{Citation |last1=Dinas |first1=Simena |title=Delaunay Triangulation |date=2020 |encyclopedia=Encyclopedia of Computer Graphics and Games |pages=1–6 |editor-last=Lee |editor-first=Newton |url=https://link.springer.com/10.1007/978-3-319-08234-9_393-1 |access-date=2025-08-19 |place=Cham |publisher=Springer International Publishing |language=en |doi=10.1007/978-3-319-08234-9_393-1 |isbn=978-3-319-08234-9 |last2=Martínez |first2=Hector J.|url-access=subscription }}</ref> 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>.<ref>{{Cite journal |last1=Matula |first1=David W. |last2=Sokal |first2=Robert R. |title=Properties of Gabriel Graphs Relevant to Geographic Variation Research and the Clustering of Points in the Plane |url=https://onlinelibrary.wiley.com/doi/10.1111/j.1538-4632.1980.tb00031.x |journal=Geographical Analysis |date=1980 |language=en |volume=12 |issue=3 |pages=205–222 |doi=10.1111/j.1538-4632.1980.tb00031.x |bibcode=1980GeoAn..12..205M |issn=0016-7363|url-access=subscription }}</ref>
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">{{cite book | last = de Berg | first = Mark | authorlink = Mark de Berg |author2=Otfried Cheong |author3=Marc van Kreveld | author4-link = Mark Overmars |author4=Mark Overmars | title = Computational Geometry: Algorithms and Applications | publisher = Springer-Verlag | year = 2008 | id = | url = http://www.cs.uu.nl/geobook/interpolation.pdf | isbn = 978-3-540-77973-5 | author2-link = Otfried Cheong }}</ref>
Given a set of edges that connect points of the plane, the problem to determine whether they contain a triangulation is NP-complete.{{sfn |Lloyd|1977}}
== Regular triangulations == 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.<ref>{{Cite web |title=How to Convert a Point Cloud to a 3D Mesh in Python and C++ |url=https://meshlib.io/feature/point-cloud-to-mesh/ |access-date=2025-08-19 |language=en-US}}</ref>
==Variants and extensions==
In addition to classical Delaunay and regular triangulations, several other forms and problems related to point-set triangulations have been studied in computational geometry. The minimum-weight triangulation (MWT) seeks a triangulation of a point set that minimizes the total edge length; although this problem was shown to be NP-hard,<ref>{{cite journal | last1=Mulzer | first1=Wolfgang | last2=Rote | first2=Günter | title=Minimum-weight triangulation is NP-hard | journal=Journal of the ACM | date=2008 | volume=55 | issue=2 | pages=1–29 | doi=10.1145/1346330.1346336 | arxiv=cs/0601002 | url=https://doi.org/10.1145/1346330.1346336 }}</ref> approximation algorithms and heuristics have been developed. A related heuristic, the greedy triangulation, constructs a triangulation by repeatedly adding the shortest edge that does not intersect existing edges, yielding good approximations in practice.<ref>{{cite journal | last1=Toussaint | first1=Godfried T. | title=The relative neighbourhood graph of a finite planar set | journal=Pattern Recognition | date=1980 | volume=12 | issue=4 | pages=261–268 | doi=10.1016/0031-3203(80)90066-7 | bibcode=1980PatRe..12..261T | url=https://doi.org/10.1016/0031-3203(80)90066-7 | url-access=subscription }}</ref> Another special type is the Pitteway triangulation, in which each edge connects a pair of points whose Voronoi cells share a boundary segment; such triangulations are closely related to the Delaunay and Gabriel graphs.<ref>{{cite journal | last1=Boulton | first1=D. M. | title=Occupancy of a rectangular array | journal=The Computer Journal | date=1973 | volume=16 | pages=57–63 | doi=10.1093/comjnl/16.1.57 | url=https://doi.org/10.1093/comjnl/16.1.57 }}</ref> Point-set triangulations can also be viewed as maximal planar straight-line graphs, since no additional straight edges can be added without destroying planarity.<ref>Fáry, I. (1948). "On straight line representation of planar graphs". ''Acta Scientiarum Mathematicarum''. 11: 229–233.</ref> More recently, machine learning approaches have been proposed to generate triangulations directly from unstructured point clouds, such as PointTriNet, which uses neural networks to learn triangulation patterns for 2D and 3D data.<ref>{{cite arXiv | last1=Sharp | first1=Nicholas | last2=Ovsjanikov | first2=Maks | title=PointTriNet: Learned Triangulation of 3D Point Sets | date=2020 | class=cs.CV | eprint=2005.02138 }}</ref> Advances in combinatorial geometry have also yielded new bounds on the number of distinct triangulations realizable on a fixed point set, highlighting the exponential complexity of these structures.<ref>{{cite arXiv | last1=Cruces | first1=Belén | last2=Huemer | first2=Clemens | last3=Lara | first3=Dolores | title=On the number of drawings of a combinatorial triangulation | date=2025 | class=math.CO | eprint=2504.17088 }}</ref>
== Combinatorics in the plane == 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>{{citation | last1 = Edelsbrunner | first1 = Herbert | author1-link = Herbert Edelsbrunner | last2 = Tan | first2 = Tiow Seng | last3 = Waupotitsch | first3 = Roman | doi = 10.1137/0913058 | issue = 4 | journal = SIAM Journal on Scientific and Statistical Computing | mr = 1166172 | pages = 994–1008 | title = An ''O''(''n''<sup>2</sup> log ''n'') time algorithm for the minmax angle triangulation | volume = 13 | year = 1992| citeseerx = 10.1.1.66.2895 }}.</ref>
== Algorithms to build triangulations in the plane == '''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 algorithms ==
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.
{| class="wikitable" style="border:none;text-align:center;" |- ! style="background:white;border:none;" colspan="2" | ! style="padding:1em;" | minimize ! style="padding:1em;" | maximize |- ! style="padding:1em;" | minimum ! rowspan="2" style="padding:1em;" | angle | bgcolor="darkgray" | | <math>O(n \log n)</math> <br /> (Delaunay triangulation) |- ! style="padding:1em;" | maximum | <math>O(n^2 \log n)</math> {{sfn |Edelsbrunner|Tan|Waupotitsch|1990}} {{sfn |Bern|Edelsbrunner|Eppstein|Mitchell|1993}} | bgcolor="darkgray" | |- ! style="padding:1em;" | minimum ! rowspan="2" style="padding:1em;" | area | <math>O(n^2)</math> {{sfn |Chazelle|Guibas|Lee|1985}} | <math>O(n^2 \log n)</math> {{sfn |Vassilev|2005}} |- ! style="padding:1em;" | maximum | <math>O(n^2 \log n)</math> {{sfn |Vassilev|2005}} | bgcolor="darkgray" | |- ! style="padding:1em;" | maximum ! rowspan="1" style="padding:1em;" | degree | NP-complete <br /> for degree of 7 {{sfn |Jansen|1992}} | bgcolor="darkgray" | |- ! style="padding:1em;" | maximum ! rowspan="1" style="padding:1em;" | eccentricity | <math>O(n^3)</math> {{sfn |Bern|Edelsbrunner|Eppstein|Mitchell|1993}} | bgcolor="darkgray" | |- ! style="padding:1em;" | minimum ! rowspan="3" style="padding:1em;" | edge length | <math>O(n \log n)</math> <br /> (Closest pair of points problem) | NP-complete {{sfn |Fekete|2012}} |- ! style="padding:1em;" | maximum | <math>O(n^2)</math> {{sfn |Edelsbrunner|Tan|1991}} | <math>O(n \log n)</math> <br /> (using the Convex hull) |- ! style="padding:1em;" | sum of | NP-hard <br /> (Minimum-weight triangulation) | bgcolor="darkgray" | |- ! style="padding:1em;" | minimum ! rowspan="1" style="padding:1em;" | height | bgcolor="darkgray" | | <math>O(n^2 \log n)</math> {{sfn |Bern|Edelsbrunner|Eppstein|Mitchell|1993}} |- ! style="padding:1em;" | maximum ! rowspan="1" style="padding:1em;" | slope | <math>O(n^3)</math> {{sfn |Bern|Edelsbrunner|Eppstein|Mitchell|1993}} | bgcolor="darkgray" | |}
==See also== *Mesh generation *Polygon triangulation
==Notes== {{reflist|colwidth=30em}}
==References== {{refbegin|colwidth=30em}} * {{citation | last1 = Bern | first1 = M. | last2 = Edelsbrunner | first2 = H. | author2-link = Herbert Edelsbrunner | last3 = Eppstein | first3 = D. | author3-link = David Eppstein | last4 = Mitchell | first4 = S. | last5 = Tan | first5 = T. S. | doi = 10.1007/BF02573962 | issue = 1 | journal = Discrete and Computational Geometry | mr = 1215322 | pages = 47–65 | title = Edge insertion for optimal triangulations | volume = 10 | year = 1993 | doi-access = free }} * {{cite journal | last1 = Chazelle | first1 = Bernard | last2 = Guibas | first2 = Leo J. | last3 = Lee | first3 = D. T. | title = The power of geometric duality | journal = BIT | volume = 25 | issue = 1 | year = 1985 | issn = 0006-3835 | pages = 76–90 | url = http://www.cs.princeton.edu/~chazelle/pubs/PowerDuality.pdf | doi = 10.1007/BF01934990 | publisher = BIT Computer Science and Numerical Mathematics | s2cid = 122411548 }} * {{cite book | last1 = de Berg | first1 = Mark | last2 = van Kreveld | first2 = Marc | last3 = Overmars | first3 = Mark | last4 = Schwarzkopf | first4 = Otfried | title = Computational Geometry: Algorithms and Applications | edition = 3 | publisher = Springer-Verlag | url = http://www.cs.uu.nl/geobook/ | year = 2008 }} * {{cite book | last1 = O'Rourke | first1 = Joseph | last2 = L. Devadoss | first2 = Satyan | author2-link = Satyan Devadoss | title = Discrete and Computational Geometry | edition = 1 | publisher = Princeton University Press | year = 2011 | ref = dcg }} * {{cite conference | last1 = Edelsbrunner | first1 = Herbert | last2 = Tan | first2 = Tiow Seng | last3 = Waupotitsch | first3 = Roman | year = 1990 | title = An O(n2log n) time algorithm for the MinMax angle triangulation | conference = Proceedings of the sixth annual symposium on Computational geometry | series = SCG '90 | pages = 44–52 | isbn = 0-89791-362-0 | doi = 10.1145/98524.98535 | publisher = ACM | citeseerx = 10.1.1.66.2895 }} * {{cite conference | last1 = Edelsbrunner | first1 = Herbert | last2 = Tan | first2 = Tiow Seng | year = 1991 | title = A quadratic time algorithm for the minmax length triangulation | conference = 32nd Annual Symposium on Foundations of Computer Science | pages = 414–423 | isbn = 0-8186-2445-0 | doi = 10.1109/SFCS.1991.185400 | citeseerx = 10.1.1.66.8959 }} * {{cite arXiv | last = Fekete | first = Sándor P. | eprint = 1208.0202v1 | title = The Complexity of MaxMin Length Triangulation | year = 2012 | class = cs.CG }} * {{cite conference | last = Jansen | first = Klaus | year = 1992 | title = The Complexity of the Min-max Degree Triangulation Problem | conference = 9th European Workshop on Computational Geometry | pages = 40–43 | url = http://tizian.cs.uni-bonn.de/EuroCG93/j-cmmdt-93.pdf }} * {{cite conference | last = Lloyd | first = Errol Lynn | conference = 18th Annual Symposium on Foundations of Computer Science (SFCS 1977) | title = On triangulations of a set of points in the plane | year = 1977 | pages = 228–240 | doi = 10.1109/SFCS.1977.21 | hdl = 1721.1/148916 | hdl-access = free }} * {{cite thesis | type = Ph.D. | first = Tzvetalin Simeonov | last = Vassilev | title = Optimal Area Triangulation | publisher = University of Saskatchewan, Saskatoon | year = 2005 | url = http://ecommons.usask.ca/bitstream/handle/10388/etd-08232005-111957/thesisFF.pdf | access-date = 2013-06-15 | archive-url = https://web.archive.org/web/20170813183040/https://ecommons.usask.ca/bitstream/handle/10388/etd-08232005-111957/thesisFF.pdf | archive-date = 2017-08-13 | url-status = dead }} {{refend}}
{{DEFAULTSORT:Point Set Triangulation}} Category:Triangulation (geometry) Category:Point (geometry)