Triangularea unei mulțimi de puncte

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

Î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}}$. Î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. Î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.

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).

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ă.

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.

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.

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.

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)
	maxim	$O(n^{2}\log n)$
arie	minimă	$O(n^{2})$	$O(n^{2}\log n)$
	maximă	$O(n^{2}\log n)$
grad	maxim	NP-completă pentru gradul 7
excentricitate	maximă	$O(n^{3})$
lungime laturi	minimă	$O(n\log n)$ (Problema perechii de puncte cele mai apropiate)	NP-completă
	maximă	$O(n^{2})$	$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)$
pantă	maximă	$O(n^{3})$

Bibliografie

• en Bern, M.; Edelsbrunner, Herbert; Eppstein, David; Mitchell, S.; Tan, T. S.,  
• en Chazelle, Bernard; Guibas, Leo J.; Lee, D. T. 
• en de Berg, Mark; van Kreveld, Marc; Overmars, Mark; Schwarzkopf, Otfried. 
• en O'Rourke, Joseph; L. Devadoss, Satyan. 
• en Edelsbrunner, Herbert; Tan, Tiow Seng; Waupotitsch, Roman. 
• en Edelsbrunner, Herbert; Tan, Tiow Seng. 
• en Fekete, Sándor P. 
• en Jansen, Klaus. 
• en Lloyd, Errol Lynn. 
• en Vassilev, Tzvetalin Simeonov. 
• en De Loera, Jesús A.; Rambau, Jörg; Santos Leal, Francisco. 
• en Devadoss, O'Rourke Discrete and Computational Geometry. Princeton University Press, 2011

Vezi și

• Triangularea unui poligon
• Triangularea unei suprafețe