Triangularea unei mulțimi de puncte

De la testwiki
Sari la navigare Sari la căutare
Două triangulări diferite ale aceleiași mulțimi de 9 puncte dintr-un plan

În Format:Ill-wd triangularea unei mulțimi de puncte 𝒫 din spațiul euclidian ℝd este un complex simplicial care acoperă înfășurătoarea convexă a lui 𝒫 și ale cărui vârfuri fac parte din 𝒫.[1] În plan (când 𝒫 este o mulțime de puncte în ℝ2), triangulările sunt formate din triunghiuri, împreună cu laturile și vârfurile acestora. Unii autori cer ca toate punctele lui 𝒫 să fie vârfuri ale triangulărilor sale.[2] În acest caz, o triangulare a unei mulțimi de puncte 𝒫 din plan poate fi definită alternativ ca un set maxim de muchii care nu se intersectează decât în punctele 𝒫. Î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 Format:Ill-wd. Triangularea Delaunay a unei mulțimi de puncte 𝒫 din plan conține graful Gabriel, graful celor mai apropiați vecini și arborele acoperitor minim al 𝒫.

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 Format:Ill-wd. 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 𝒫⊂ℝd pot fi obținute prin transferarea punctelor 𝒫 în ℝd+1 (ceea ce înseamnă adăugarea unei coordonate xd+1 fiecărui punct al 𝒫), prin calculul înfășurătoarei convexe a mulțimii de puncte transferate și prin proiectarea Format:Mvar-fețelor acestei înfășurătoare convexe înapoi în ℝd. Triangulările construite în acest fel sunt denumite triangulări regulate ale 𝒫. Când punctele sunt transferate pe paraboloidul ecuației xd+1=x12+⋯+xd2, această construcție are ca rezultat triangularea Delaunay a mulțimii 𝒫. 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 𝒫 nu se află în aceeași sferă.

Combinatorică în plan

Orice triangulare a oricărei mulțimi 𝒫 de n puncte din plan are 2n−h−2 triunghiuri și 3n−h−3 muchii unde h este numărul de puncte ale lui 𝒫 de pe frontiera înfășurătoarei convexe a mulțimii 𝒫. 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 𝒫 ș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 𝒫 în funcție de coordonatele Format:Mvar. Primele trei puncte determină un triunghi. Se ia în considerare următorul punct Format:Mvar din mulțimea ordonată și se conectează cu toate punctele considerate anterior {p1,...,pk} care sunt vizibile din Format:Mvar. Se continuă acest proces de adăugare la un moment dat a câte un punct din 𝒫 până când toate elementele 𝒫 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 Format:Mvar este numărul de puncte.

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

Note

  1. ↑ De Loera, 2010
  2. ↑ de Berg, 2008, secțiunea 9.1
  3. ↑ de Berg, 2008
  4. ↑ Lloyd, 1977
  5. ↑ Edelsbrunner, 1992
  6. ↑ Devadoss, 2011, p. 60
  7. ↑ Devadoss, 2011, p. 62
  8. ↑ Edelsbrunner, 1990
  9. ↑ 9,0 9,1 9,2 9,3 Bern, 1993
  10. ↑ Chazelle, 1985
  11. ↑ 11,0 11,1 Vassilev, 2005
  12. ↑ Jansen, 1992
  13. ↑ Fekete, 2012
  14. ↑ Edelsbrunner, 1991

Bibliografie

Vezi și

Format:Portal

de:Gitter (Geometrie)#Dreiecksgitter

Adus de la „https://ro.wiki.beta.math.wmflabs.org/w/index.php?title=Triangularea_unei_mulțimi_de_puncte&oldid=2931”