213.106.56.145: added date to patent

2014-12-31T17:15:53Z

added date to patent

en>Smartyhall: Disambiguated: ROM → Read-only memory

2014-01-27T16:58:22Z

New page

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''1 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''1 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> ([[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]] 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> ([[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> (using the [[Convex hull algorithms|Convex hull]])
|-
! style="padding:1em;" | sum of
| [[NP-hard]] ([[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]]

Algebraic code-excited linear prediction - Revision history

213.106.56.145: added date to patent

en>Smartyhall: Disambiguated: ROM → Read-only memory