Vizualizare sursă pentru „Triangularea unei mulțimi de puncte”

[[Fișier:PointSetTriangulations.svg|thumb|Două triangulări diferite ale aceleiași [[mulțime |mulțimi]] de 9 [[punct (geometrie) |puncte]] dintr-un [[plan (geometrie) |plan]] ]]
În {{ill-wd| Q874709||geometria algoritmică}} '''triangularea unei mulțimi de puncte''' <math>\mathcal{P}</math> din [[spațiu euclidian |spațiul euclidian]] <math>\mathbb{R}^d</math> este un [[complex simplicial]] care acoperă [[înfășurătoare convexă |înfășurătoarea convexă]] a lui <math>\mathcal{P}</math> și ale cărui [[vârf (geometrie) |vârfuri]] fac parte din <math>\mathcal{P}</math>.<ref>De Loera, 2010</ref> În [[plan (geometrie) |plan]] (când <math>\mathcal{P}</math> este o [[mulțime]] de [[punct (geometrie) |puncte]] în <math>\mathbb{R}^2</math>), triangulările sunt formate din triunghiuri, împreună cu [[latură (geometrie) |laturile]] și vârfurile acestora. Unii autori cer ca toate punctele lui <math>\mathcal{P}</math> să fie vârfuri ale triangulărilor sale.<ref>de Berg, 2008, secțiunea&nbsp;9.1</ref> În acest caz, o triangulare a unei mulțimi de puncte <math>\mathcal{P}</math> din plan poate fi definită alternativ ca un set maxim de muchii care nu se [[intersecție (matematică) |intersectează]] decât în punctele <math>\mathcal{P} </math>. În plan, triangulările sunt cazuri particulare [[graf planar |grafuri planare]] cu muchii drepte.

Un tip deosebit de interesant de triangulări sunt [[triangularea Delaunay paralelă |triangulările Delaunay]]. Ele sunt [[politop dual |dualurile geometrice]] ale {{ill-wd| Q757267||diagramelor Voronoi}}. Triangularea Delaunay a unei mulțimi de puncte <math>\mathcal{P}</math> din plan conține [[graf Gabriel |graful Gabriel]], [[graful celor mai apropiați vecini]] și [[Arbore minim de acoperire|arborele acoperitor minim]] al <math>\mathcal{P}</math>.

Triangulările au o serie de aplicații și există un interes de a găsi triangulările „bune” ale unei mulțimi de puncte date stabilite în baza unor criterii, cum ar fi, de exemplu {{ill-wd| Q6865406||triangularea cu pondere minimă}}. Uneori este de dorit să existe o triangulare cu proprietăți speciale, de exemplu, în care toate triunghiurile au unghiuri mari (triunghiurile lungi și înguste&nbsp;— „așchii”&nbsp;— sunt evitate).<ref>de Berg, 2008</ref>

Având în vedere un set de muchii care conectează punctele din plan, problema de a determina dacă acestea formează o triangulare este [[NP-completitudine |NP-completă]].<ref>Lloyd, 1977</ref>

== Triangulări regulate ==
Unele triangulări ale unei mulțimi de puncte <math>\mathcal{P}\subset\mathbb{R}^d</math> pot fi obținute prin transferarea punctelor <math>\mathcal{P}</math> în <math>\mathbb{R}^{d+1}</math> (ceea ce înseamnă adăugarea unei coordonate <math>x_{d+1}</math> fiecărui punct al <math>\mathcal{P}</math>), prin calculul înfășurătoarei convexe a mulțimii de puncte transferate și prin proiectarea {{mvar|d}}-[[față (geometrie) |fețelor]] acestei înfășurătoare convexe înapoi în <math>\mathbb{R}^d</math>. Triangulările construite în acest fel sunt denumite '''triangulări regulate''' ale <math>\mathcal{P}</math>. Când punctele sunt transferate pe paraboloidul ecuației <math>x_{d+1} = x_1^2+\cdots+x_d^2</math>, această construcție are ca rezultat triangularea Delaunay a mulțimii <math>\mathcal{P}</math>. De reținut că pentru ca această construcție să ofere o triangulare, înfășurătoarea convexă a mulțimii de puncte trebuie să fie un politop simplicial. În cazul triangulărilor Delaunay, aceasta înseamnă că niciun punct <math>d+2</math> al <math>\mathcal{P}</math> nu se află în aceeași [[sferă]].

== Combinatorică în plan ==
Orice triangulare a oricărei mulțimi <math>\mathcal{P}</math> de <math>n</math> puncte din plan are <math>2n - h - 2</math> triunghiuri și <math>3n - h - 3</math> muchii unde <math>h</math> este numărul de puncte ale lui <math>\mathcal{P}</math> de pe [[frontieră (topologie) |frontiera]] înfășurătoarei convexe a mulțimii <math> \mathcal{P}</math>. Acest fapt rezultă simplu din [[caracteristică Euler |caracteristica Euler]].<ref>Edelsbrunner, 1992</ref>

== Algoritmi de triangulare în plan ==
'''Algoritmul de divizare a triunghiului''': Se calculează înfășurătoarea convexă a mulțimii de puncte <math>\mathcal{P}</math> și se triangulează această înfășurătoare [[triangularea unui poligon |ca un poligon]]. Se alege un punct interior și se trasează muchii la cele trei vârfuri ale triunghiului care îl conține. Se continuă acest proces până când toate punctele interioare sunt epuizate.<ref>Devadoss, 2011, p.&nbsp;60</ref>

'''Algoritmul incremental''': Se sortează punctele <math>\mathcal{P}</math> în funcție de coordonatele {{mvar|x}}. Primele trei puncte determină un triunghi. Se ia în considerare următorul punct {{mvar|p}} din mulțimea ordonată și se conectează cu toate punctele considerate anterior <math>\{p_1,..., p_k\}</math> care sunt vizibile din {{mvar|p}}. Se continuă acest proces de adăugare la un moment dat a câte un punct din <math>\mathcal{P}</math> până când toate elementele <math>\mathcal{P}</math> au fost procesate.<ref>Devadoss, 2011, p.&nbsp;62</ref>

== Complexitatea în timp a diferiților algoritmi ==
Următorul tabel prezintă rezultatele complexității în timp pentru construcția triangulărilor mulțimii de puncte din plan, pentru diferite criterii de optimizare, unde {{mvar|n}} este numărul de puncte.
{| class="wikitable" style="border:none; text-align:center;"
|-
! style="background:white;border:none;" colspan="2" |
! style="padding:1em;" | minimizare
! style="padding:1em;" | maximizare
|-
! rowspan="2" style="padding:1em;" | unghi
! style="padding:1em;" | minim
| bgcolor="darkgray" |
| <math>O(n \log n)</math> <br /> (triangulare Delaunay)
|-
! style="padding:1em;" | maxim
| <math>O(n^2 \log n)</math><ref name=E>Edelsbrunner, 1990</ref><ref name=B>Bern, 1993</ref>
| bgcolor="darkgray" |
|-
! rowspan="2" style="padding:1em;" | arie
! style="padding:1em;" | minimă
| <math>O(n^2)</math><ref>Chazelle, 1985</ref>
| <math>O(n^2 \log n)</math><ref name=V>Vassilev, 2005</ref>
|-
! style="padding:1em;" | maximă
| <math>O(n^2 \log n)</math><ref name=V/>
| bgcolor="darkgray" |
|-
! rowspan="1" style="padding:1em;" | grad
! style="padding:1em;" | maxim
| NP-completă<br />pentru gradul 7<ref>Jansen, 1992</ref>
| bgcolor="darkgray" |
|-
! rowspan="1" style="padding:1em;" | excentricitate
! style="padding:1em;" | maximă
| <math>O(n^3)</math><ref name=B/>
| bgcolor="darkgray" |
|-
! rowspan="3" style="padding:1em;" | lungime<br/>laturi
! style="padding:1em;" | minimă
| <math>O(n \log n)</math> <br />(Problema perechii de puncte cele mai apropiate)
| NP-completă<ref>Fekete, 2012</ref>
|-
! style="padding:1em;" | maximă
| <math>O(n^2)</math><ref>Edelsbrunner, 1991</ref>
| <math>O(n \log n)</math> <br /> (folosind înfășurătoarea convexă)
|-
! style="padding:1em;" | suma lor
| [[NP-hard]] <br /> (Triangulare cu pondere minimă)
| bgcolor="darkgray" |
|-
! rowspan="1" style="padding:1em;" | înălțime
! style="padding:1em;" | minimă
| bgcolor="darkgray" |
| <math>O(n^2 \log n)</math><ref name=B/>
|-
! rowspan="1" style="padding:1em;" | pantă
! style="padding:1em;" | maximă
| <math>O(n^3)</math><ref name=B/>
| bgcolor="darkgray" |
|}

== Note ==
<references responsive/>

== Bibliografie ==
* {{en icon}} {{citation
 | last1 = Bern | first1 = M.
 | last2 = Edelsbrunner | first2 = Herbert
 | last3 = Eppstein | first3 = David
 | 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
 }}
* {{en icon}} {{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
 }}
* {{en icon}} {{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
 }}
* {{en icon}} {{cite book
 | last1 = O'Rourke | first1 = Joseph
 | last2 = L. Devadoss | first2 = Satyan
 | title = Discrete and Computational Geometry
 | edition = 1
 | publisher = Princeton University Press
 | year = 2011
 | ref = dcg
}}
* {{en icon}} {{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
 }}
* {{en icon}} {{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
 }}
* {{en icon}} {{cite arXiv
 | last = Fekete
 | first = Sándor P.
 | eprint = 1208.0202v1
 | title = The Complexity of MaxMin Length Triangulation
 | year = 2012
 | class = cs.CG
 }}
* {{en icon}} {{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
 }}
* {{en icon}} {{cite conference
 | last = Lloyd
 | first = Errol Lynn
 | year = 1977
 | title = On triangulations of a set of points in the plane
 | journal = Switching and Automata Theory, 1974., IEEE Conference Record of 15Th Annual Symposium on
 | conference = 18th Annual Symposium on Foundations of Computer Science
 | pages = 228–240
 | issn = 0272-5428
 | doi = 10.1109/SFCS.1977.21
 }}
* {{en icon}} {{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
 }}
* {{en icon}} {{cite book
 | last1 = De Loera | first1 = Jesús A.
 | last2 = Rambau | first2 = Jörg
 | last3 = Santos Leal | first3 = Francisco
 | year = 2010
 | title = Triangulations, Structures for Algorithms and Applications
 | series = Algorithms and Computation in Mathematics
 | volume = 25
 | publisher = Springer
 }}
* {{en icon}} Devadoss, O'Rourke ''Discrete and Computational Geometry''. Princeton University Press, 2011

== Vezi și ==
* [[Triangularea unui poligon]]
* [[Triangularea unei suprafețe]]

{{Portal|Matematică}}

[[Categorie:Triangulare|Punct]]

[[de:Gitter (Geometrie)#Dreiecksgitter]]