德勞內三角剖分（Delaunay triangulation）
/ duh-loh-NAY /
給定平面上一撒點，把它們連成三角形的方法有很多。大多很醜——滿是細長的薄片。德勞內三角剖分是典範的「最佳」那一個：它把點連成盡可能肥胖、形狀良好的三角形，靠一條聽來近乎神奇的規則：點集中沒有任何點被允許落在任一三角形外接圓的內部。處處是空圓。
形式上，對平面上一個（一般位置、無四點共圓的）點集 P，德勞內三角剖分 DT(P) 是唯一一個三角剖分，其中每個三角形的外接圓內部都不含 P 中任何點——即空外接圓性質。等價的刻畫：它在 P 的所有三角剖分中極大化最小角（故盡量避開薄片），而且它是沃羅諾伊圖的直線對偶——兩點以一條德勞內邊相連，恰當它們的沃羅諾伊胞腔共有一條邊。你可以用翻邊增量地建造它（翻動任何違反空圓測試的邊，重複直到無剩），用分治或掃描線演算法在 O(n log n) 內建，或把點抬升到高一維的拋物面上取下凸包——德勞內三角剖分字面上就是那個凸包的投影，把它繫上凸包演算法。
德勞內三角剖分在計算幾何、網格化與圖學中是基礎：它替有限元模擬給出高品質網格，是散布資料插值與曲面重建的自然連接，而在曲面上，（內蘊）德勞內條件正是保證餘切拉普拉斯算子權重非負的條件，把網格品質繫上離散微分幾何。誠實的告誡：極大化最小角的最優性是二維特有的——在三維中，德勞內四面體剖分儘管有空球性質，仍可能含有薄片（近乎扁平的四面體），所以三維網格品質需要額外功夫；而退化（共圓點）使三角剖分不唯一，在穩健的程式碼中需要打破平手的規則或符號擾動。
取四個構成一個細長、近乎扁平四邊形的點。把它分成兩個三角形有兩種方式，德勞內的選擇是那條對角線：使任一三角形的外接圓都不含第四個點——也就是讓兩三角形最肥的那次翻邊。翻邊演算法從任意三角剖分起步，反覆套用正是這個局部測試，直到每條邊都通過，收斂到 DT(P)。
兩條可能對角線中，德勞內選外接圓為空的那條——較肥的那對三角形。
極大化最小角的最優性是二維現象：三維的德勞內四面體剖分儘管有空球性質仍容許薄片，所以別假定德勞內在高維就意味「好網格」。共圓（退化）的輸入使三角剖分不唯一，為求穩健需要謹慎打破平手。