thumb|Delaunay-triangulatie met omgeschreven cirkels
De delaunay-triangulatie is in de computationele geometrie een triangulatie op een discrete verzameling punten, bestaande uit een netwerk van driehoeken met als hoekpunten de punten van de verzameling. Daarbij geldt voor elke driehoek dat er in de omgeschreven cirkel van de driehoek geen enkel ander punt van de verzameling mag liggen. De delaunay-triangulatie is naar de Russische wiskundige Boris Delaunay of Delone genoemd. Delaunay is de Franse manier om zijn naam te schrijven.
Als alle punten in de verzameling op dezelfde lijn liggen, is er geen delaunay-triangulatie mogelijk. Als er vier of meer punten op dezelfde cirkel liggen, bijvoorbeeld de hoekpunten van een rechthoek of een regelmatige zeshoek, zijn er meer delaunay-triangulaties mogelijk: men kan dan kiezen welke drie punten men tot een driehoek verbindt.
De delaunay-triangulatie heeft als eigenschap, dat het de kleinste hoek van alle driehoeken in de triangulatie maximaliseert, en zo weinig mogelijk driehoeken met scherpe hoeken genereert. Dit is in de computergraphics gewenst omdat het de kans op afrondingsfouten verkleint. De delaunay-triangulatie wordt onder meer toegepast voor het construeren van een niet-uniform rooster voor eindige-elementenmethoden. De delaunay-triangulatie kan naar meer dimensies worden uitgebreid. In het driedimensionale geval moet men tussen vier punten van de verzameling viervlakken vinden, dus opgebouwd uit vier driehoeken, waarvoor geldt dat in de omgeschreven bol geen andere punten liggen.
Verband met voronoi-diagrammen In de grafentheorie is de delaunay-triangulatie van een discrete verzameling punten in het vlak een planaire graaf, en wel de duale graaf van het voronoi-diagram van die verzameling. De hoekpunten van de voronoi-cellen zijn de middelpunten van de omgeschreven cirkels van de driehoeken van de delaunay-triangulatie. Het zijn, met andere woorden, de snijpunten van de middelloodlijnen van de drie zijden van elke driehoek.
Als twee punten in de delaunay-triangulatie verbonden zijn, hebben de voronoi-cellen van die punten een gemeenschappelijke zijde, en omgekeerd.
Algoritme Er bestaan verschillende algoritmen voor het maken van een delaunay-triangulatie. Een eenvoudig algoritme in twee dimensies is het spiegel-algoritme. Dat gaat uit van een willekeurige triangulatie van de verzameling van discrete punten. Van elke driehoek wordt dan onderzocht of zijn omgeschreven cirkel het derde hoekpunt van een aangrenzende driehoek omvat. Zo ja, dan is niet voldaan aan de delaunay-voorwaarde. De eerste figuur beneden geeft daar een voorbeeld van. Door om de gemeenschappelijke zijde van de twee driehoeken te spiegelen, zoals in de tweede figuur beneden, wordt er wel aan voldaan, althans lokaal. Door de spiegeling kan echter de delaunay-voorwaarde in de aangrenzende driehoeken weer ongedaan zijn gemaakt. In het slechtste geval moeten na een spiegeling alle andere driehoeken opnieuw worden onderzocht. Het algoritme heeft daarom een looptijd van .
Er bestaan efficiëntere algoritmen; de beste hebben een looptijd van . Tot die algoritmen behoren: de incrementele constructie van een triangulatie, waarbij de punten een voor een aan de triangulatie worden toegevoegd, het sweepline-algoritme, waarbij ook telkens nieuwe driehoeken aan de triangulatie worden toegevoegd die ontstaan door een horizontale lijn van onder naar boven over het vlak te laten sweepen, verdeel-en-heers-algoritmen, die de triangulatie opbouwen door kleinere delaunay-triangulaties te verbinden met behoud van de delaunay-voorwaarde.
Deelgrafen Gabrielgraaf, deelgraaf van de delaunay-triangulatie Urquhartgraaf Relative neighborhood graph
Websites . Triangl A Two-Dimensional Quality Mesh Generator and Delaunay Triangulator, software voor het maken van delaunay-triangulaties en voronoi-diagrammen
Categorie:Grafentheorie Categorie:Meetkunde