Delunijeva triangulacija

U matematici i računarskoj geometriji, Delunijeva triangulacija za dati skup diskretnih tačaka $P$ u opštem položaju je triangulacija $DT(P)$ takva da nijedna tačka u $P$ nije unutar opisanog kruga bilo kog trougla u $DT(P)$ . Delunijeve triangulacije maksimiziraju minimalni ugao svih uglova trouglova u triangulaciji; pri tome se izbjegavaju trouglovi sa dva veoma oštra ugla. Triangulacija je dobila ime po Borisu Deluniju za njegov rad na na ovu temu iz 1934. godine.^[1]

Za skup tačaka na istoj pravoj ne postoji Delunijeva triangulacija. Za četiri ili više tačake na istoj kružnici (npr. temena pravougaonika) Delunijeva triangulacija nije jedinstvena: obe moguće triangulacije koje dele četvorougao na dva trougla zadovoljavaju „Delunijev uslov“, tj. zahtev da opisani krugovi svih trouglova imaju praznu unutrašnjost.

Razmatranjem ograničenih sfera, pojam Delunijeve triangulacije proteže se na tri i više dimenzija. Moguće su generalizacije i za metrike koje nisu euklidske. Međutim, u ovim slučajevima nije zagarantovano da postoji ili može biti jedinstvena Delunijeva triangulacija.

Reference uredi

^ Delaunay, Boris (1934). „Sur la sphère vide”. Bulletin de l'Académie des Sciences de l'URSS, Classe des Sciences Mathématiques et Naturelles. 6: 793—800.

Spoljašnje veze uredi

"Delaunay triangulation". Wolfram MathWorld
Delaunay triangulation in CGAL, the Computational Geometry Algorithms Library:
- Mariette Yvinec. 2D Triangulation
- Pion, Sylvain; Teillaud, Monique. 3D Triangulations
- Hornus, Samuel; Devillers, Olivier; Jamin, Clément. dD Triangulations
- Hert, Susan; Seel, Michael. dD Convex Hulls and Delaunay Triangulations
"Poly2Tri: Incremental constrained Delaunay triangulation. Open source C++ implementation
"Divide & Conquer Delaunay triangulation construction". Open source C99 implementation

[Delaunay1934-1] Delaunay, Boris (1934). „Sur la sphère vide”. Bulletin de l'Académie des Sciences de l'URSS, Classe des Sciences Mathématiques et Naturelles. 6: 793—800.

[1]