Delaunay üçgenlemesi
Hiçbir noktanın herhangi bir üçgenin çevrel çemberinin içinde kalmamasını sağlayarak en küçük açıyı en büyük yapan üçgenleme.
Koşulu 1934’te Boris Delaunay ortaya koydu. Bir nokta kümesini üçgenlemenin sayısız yolu arasından Delaunay, uzun ve ince “sliver” üçgenlerden kaçınanı seçer; boş çember koşulu üçgenleri olabildiğince düzgün biçimli olmaya zorlar. Voronoi diyagramının geometrik dualidir.
Oyunlarda ve grafikte arazi (yükseklik verisinden TIN modelleri), düzgün biçimli ağ üretimi ve navmesh’lerin temeli olarak kullanılır. Yaygın algoritmaları Bowyer–Watson (artımlı çember testleri) ve böl-ve-yönet yöntemidir. Kulak kesmeden farkı, yüzeyi üçgenlere bölmekle yetinmeyip o üçgenlerin kalitesini de önemsemesidir.