Triangulacja Delaunaya
Triangulacja maksymalizująca najmniejszy kąt, w której żaden punkt nie leży wewnątrz okręgu opisanego na żadnym trójkącie.
Warunek sformułował Boris Delone (Delaunay) w 1934 roku. Spośród wszystkich sposobów triangulacji zbioru punktów wybiera ona ten, który unika długich, cienkich trójkątów-„drzazg” — warunek pustego okręgu wymusza trójkąty o możliwie dobrych proporcjach. Jest geometrycznie dualna wobec diagramu Woronoja.
W grach i grafice służy do modelowania terenu (siatki TIN z map wysokości), generowania poprawnych siatek oraz jako podstawa navmeshy. Typowe algorytmy to Bowyera–Watsona (przyrostowe testy okręgów) i „dziel i zwyciężaj”. W odróżnieniu od ear clipping nie chodzi tu tylko o pocięcie powierzchni na trójkąty, lecz o ich jakość.