Делунијева триангулација

У математици и рачунарској геометрији, Делунијева триангулација за дати скуп дискретних тачака $P$ у општем положају је триангулација $DT(P)$ таква да ниједна тачка у $P$ није унутар описаног круга било ког троугла у $DT(P)$ . Делунијеве триангулације максимизирају минимални угао свих углова троуглова у триангулацији; при томе се избјегавају троуглови са два веома оштра угла. Триангулација је добила име по Борису Делунију за његов рад на на ову тему из 1934. године.^[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.

Спољашње везе уреди

"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]