View source for Algebraic code-excited linear prediction

A '''triangulation of a set of points''' '''P''' in the [[plane (geometry)|plane]] is a [[Polygon triangulation|triangulation]] of the [[convex hull]] of '''P''', with all points from '''P''' being among the vertices of the triangulation.{{sfn |de Berg|van Kreveld|Overmars|Schwarzkopf|2008|loc=Section 9.1}} Triangulations are special cases of [[planar straight-line graph]]s.

There are special triangulations like the [[Delaunay triangulation]] which is the [[Dual polytope|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).

Given a set of edges that connect some pairs of the points, the problem to determine whether they contain a triangulation is [[NP-complete]] .{{sfn |Lloyd|1977}}

==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''<sub>1</sub> in the space of dimension larger by 1 which are the projections of the original point set onto the paraboloid surface <math>x_{n+1} = x_1^2+\cdots+x_n^2</math>. One has to construct the convex hull of the set ''S''<sub>1</sub> 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 [[facet (geometry)|facet]]s.

== Complexities ==

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

{| 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 algorithms|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==
*[[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
 | ref = harv
}}
* {{cite journal
 | last1 = Chazelle | first1 = Bernard
 | last2 = Guibas | first1 = 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
 | ref = harv
}}
* {{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
 | ref = harv
}}
* {{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
 | booktitle = Proceedings of the sixth annual symposium on Computational geometry
 | series = SCG '90
 | pages = 44–52
 | url = http://doi.acm.org/10.1145/98524.98535
 | isbn = 0-89791-362-0
 | doi = 10.1145/98524.98535
 | publisher = ACM
 | ref = harv
}}
* {{cite conference
 | last1 = Edelsbrunner | first1 = Herbert
 | last2 = Tan | first2 = Tiow Seng
 | year = 1991
 | title = A quadratic time algorithm for the minmax length triangulation
 | booktitle = 32nd Annual Symposium on Foundations of Computer Science
 | pages = 414–423
 | url = http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=185400
 | isbn = 0-8186-2445-0
 | doi = 10.1109/SFCS.1991.185400
 | ref = harv
}}
* {{cite arXiv
 | last = Fekete
 | first = Sándor P.
 | eprint = 1208.0202
 | title = The Complexity of MaxMin Length Triangulation
 | year = 2012
 | version = v1
 | ref = harv
}}
* {{cite conference
 | last = Jansen
 | first = Klaus
 | year = 1992
 | title = The Complexity of the Min-max Degree Triangulation Problem
 | booktitle = 9th European Workshop on Computational Geometry
 | pages = 40–43
 | url = http://tizian.cs.uni-bonn.de/EuroCG93/j-cmmdt-93.pdf
 | ref = harv
}}
* {{cite conference
 | last = Lloyd
 | first = Errol Lynn
 | year = 1977
 | title = On triangulations of a set of points in the plane
 | booktitle = 18th Annual Symposium on Foundations of Computer Science
 | pages = 228–240
 | url = http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=4567947
 | issn = 0272-5428
 | doi = 10.1109/SFCS.1977.21
 | ref = harv
}}
* {{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
 | ref = harv
}}
{{refend}}

{{DEFAULTSORT:Point Set Triangulation}}
[[Category:Triangulation (geometry)]]

[[de:Gitter (Geometrie)#Dreiecksgitter]]
[[fr:Triangulation d'un ensemble de points]]