Triangularea unei mulțimi de puncte

În geometria algoritmică^⁠(d) triangularea unei mulțimi de puncte ${\mathcal {P}}$ din spațiul euclidian $\mathbb {R} ^{d}$ este un complex simplicial care acoperă înfășurătoarea convexă a lui ${\mathcal {P}}$ și ale cărui vârfuri fac parte din ${\mathcal {P}}$ .^[1] În plan (când ${\mathcal {P}}$ este o mulțime de puncte în $\mathbb {R} ^{2}$ ), triangulările sunt formate din triunghiuri, împreună cu laturile și vârfurile acestora. Unii autori cer ca toate punctele lui ${\mathcal {P}}$ să fie vârfuri ale triangulărilor sale.^[2] În acest caz, o triangulare a unei mulțimi de puncte ${\mathcal {P}}$ din plan poate fi definită alternativ ca un set maxim de muchii care nu se intersectează decât în punctele ${\mathcal {P}}$ . În plan, triangulările sunt cazuri particulare grafuri planare cu muchii drepte.

Două triangulări diferite ale aceleiași mulțimi de 9 puncte dintr-un plan

Un tip deosebit de interesant de triangulări sunt triangulările Delaunay. Ele sunt dualurile geometrice ale diagramelor Voronoi^⁠(d). Triangularea Delaunay a unei mulțimi de puncte ${\mathcal {P}}$ din plan conține graful Gabriel, graful celor mai apropiați vecini și arborele acoperitor minim al ${\mathcal {P}}$ .

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 triangularea cu pondere minimă^⁠(d). 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 — „așchii” — sunt evitate).^[3]

Având în vedere un set de muchii care conectează punctele din plan, problema de a determina dacă acestea formează o triangulare este NP-completă.^[4]

Triangulări regulate

Unele triangulări ale unei mulțimi de puncte ${\mathcal {P}}\subset \mathbb {R} ^{d}$ pot fi obținute prin transferarea punctelor ${\mathcal {P}}$ în $\mathbb {R} ^{d+1}$ (ceea ce înseamnă adăugarea unei coordonate $x_{d+1}$ fiecărui punct al ${\mathcal {P}}$ ), prin calculul înfășurătoarei convexe a mulțimii de puncte transferate și prin proiectarea $d$ -fețelor acestei înfășurătoare convexe înapoi în $\mathbb {R} ^{d}$ . Triangulările construite în acest fel sunt denumite triangulări regulate ale ${\mathcal {P}}$ . Când punctele sunt transferate pe paraboloidul ecuației $x_{d+1}=x_{1}^{2}+\cdots +x_{d}^{2}$ , această construcție are ca rezultat triangularea Delaunay a mulțimii ${\mathcal {P}}$ . 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 $d+2$ al ${\mathcal {P}}$ nu se află în aceeași sferă.

Combinatorică în plan

Orice triangulare a oricărei mulțimi ${\mathcal {P}}$ de $n$ puncte din plan are $2n-h-2$ triunghiuri și $3n-h-3$ muchii unde $h$ este numărul de puncte ale lui ${\mathcal {P}}$ de pe frontiera înfășurătoarei convexe a mulțimii ${\mathcal {P}}$ . Acest fapt rezultă simplu din caracteristica Euler.^[5]

Algoritmi de triangulare în plan

Algoritmul de divizare a triunghiului: Se calculează înfășurătoarea convexă a mulțimii de puncte ${\mathcal {P}}$ și se triangulează această înfășurătoare 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.^[6]

Algoritmul incremental: Se sortează punctele ${\mathcal {P}}$ în funcție de coordonatele $x$ . Primele trei puncte determină un triunghi. Se ia în considerare următorul punct $p$ din mulțimea ordonată și se conectează cu toate punctele considerate anterior $\{p_{1},...,p_{k}\}$ care sunt vizibile din $p$ . Se continuă acest proces de adăugare la un moment dat a câte un punct din ${\mathcal {P}}$ până când toate elementele ${\mathcal {P}}$ au fost procesate.^[7]

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 $n$ este numărul de puncte.

		minimizare	maximizare
unghi	minim		$O(n\log n)$ (triangulare Delaunay)
unghi	maxim	$O(n^{2}\log n)$ ^[8]^[9]
arie	minimă	$O(n^{2})$ ^[10]	$O(n^{2}\log n)$ ^[11]
arie	maximă	$O(n^{2}\log n)$ ^[11]
grad	maxim	NP-completă pentru gradul 7^[12]
excentricitate	maximă	$O(n^{3})$ ^[9]
lungime laturi	minimă	$O(n\log n)$ (Problema perechii de puncte cele mai apropiate)	NP-completă^[13]
	maximă	$O(n^{2})$ ^[14]	$O(n\log n)$ (folosind înfășurătoarea convexă)
	suma lor	NP-hard (Triangulare cu pondere minimă)
înălțime	minimă		$O(n^{2}\log n)$ ^[9]
pantă	maximă	$O(n^{3})$ ^[9]

Note

^ De Loera, 2010
^ de Berg, 2008, secțiunea 9.1
^ de Berg, 2008
^ Lloyd, 1977
^ Edelsbrunner, 1992
^ Devadoss, 2011, p. 60
^ Devadoss, 2011, p. 62
^ Edelsbrunner, 1990
^ ^a ^b ^c ^d Bern, 1993
^ Chazelle, 1985
^ ^a ^b Vassilev, 2005
^ Jansen, 1992
^ Fekete, 2012
^ Edelsbrunner, 1991

Bibliografie

en Bern, M.; Edelsbrunner, Herbert; Eppstein, David; 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
en Chazelle, Bernard; Guibas, Leo J.; Lee, D. T. (1985). „The power of geometric duality” (PDF). BIT. BIT Computer Science and Numerical Mathematics. 25 (1): 76–90. doi:10.1007/BF01934990. ISSN 0006-3835.
en de Berg, Mark; van Kreveld, Marc; Overmars, Mark; Schwarzkopf, Otfried (2008). Computational Geometry: Algorithms and Applications (ed. 3). Springer-Verlag.
en O'Rourke, Joseph; L. Devadoss, Satyan (2011). Discrete and Computational Geometry (ed. 1). Princeton University Press.
en 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.
en 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.
en Fekete, Sándor P. (2012). „The Complexity of MaxMin Length Triangulation”. arXiv:1208.0202v1  [cs.CG].
en Jansen, Klaus (1992). The Complexity of the Min-max Degree Triangulation Problem (PDF). 9th European Workshop on Computational Geometry. pp. 40–43.
en 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.
en Vassilev, Tzvetalin Simeonov (2005). Optimal Area Triangulation (PDF) (Ph.D.). University of Saskatchewan, Saskatoon. Arhivat din original (PDF) la 13 august 2017. Accesat în 15 iunie 2013.
en De Loera, Jesús A.; Rambau, Jörg; Santos Leal, Francisco (2010). Triangulations, Structures for Algorithms and Applications. Algorithms and Computation in Mathematics. 25. Springer.
en Devadoss, O'Rourke Discrete and Computational Geometry. Princeton University Press, 2011

Vezi și

Portal Matematică

[1] De Loera, 2010

[2] Berg, 2008, secțiunea 9.1

[3] Berg, 2008

[4] Lloyd, 1977

[5] Edelsbrunner, 1992

[6] Devadoss, 2011, p. 60

[7] Devadoss, 2011, p. 62

[E-8] Edelsbrunner, 1990

[B-9] Bern, 1993

[10] Chazelle, 1985

[V-11] Vassilev, 2005

[12] Jansen, 1992

[13] Fekete, 2012

[14] Edelsbrunner, 1991

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]