Delaunaytriangulering

Delaunaytriangulering är en triangulering av en mängd punkter i planet där cirkeln som omsluter varje triangle (omkretscirkeln) inte innehåller några andra givna punkter inuti. Denna tomrumscirkeln-egenskap gör trianguleringen särskilt lämplig för geometriiska beräkningar och mesh-generation. Delaunaytrianguleringens dual är Voronoi-diagrammet; varje triangels kant korresponderar mot en kant i Voronoi-diagrammet.

En annan viktig egenskap är att Delaunaytriangulering ofta maximerar den minsta vinkeln bland trianglarna, vilket minimerar förekomsten av mycket smala trianglar och leder till mer kvalitativa trianguleringar för numeriska tillämpningar.

Om inga fyra punkter ligger på samma cirkel (inga cocirkulära fyrkanter) är trianguleringen unik. Vid cocirkulära konfigurationer kan flera trianguleringar uppfylla tomrumscirkels-egenskapen.

Algos och komplexitet: det finns flera sätt att konstruera en Delaunaytriangulering. Vanliga metoder är Bowyer–Watson-algoritmen och andra inkrementella tekniker samt divide-and-conquer-strategier. I praktiken uppnås ofta byggtider nära O(n log n) i medelfall, medan den teoretiska garantin varierar beroende på implementering och indata. Robusthet mot numeriska fel uppnås vanligtvis genom exakta predikat och försiktiga numeriska tekniker.

Varianter och tillämpningar: Constrained Delaunay triangulation bevarar angivna kanter eller kanter på en polygon. Delaunay-trianguleringar används inom finite element-metoder, datorgrafik, geografiska informationssystem och terrängmodellering. I 3D gäller Delaunay-tetrahedralering som motsvarar dess rumsliga motsvarighet.