德勞內三角剖分（Delaunay triangulation）
/ duh-loh-NAY /
給測量員一堆量測過的散點，請他把點連成三角形。連法很多，但大多會產出醜陋的細片——又長又薄、近乎扁平的三角形，會毀掉計算。德勞內三角剖分是唯一一種盡量避開這些細片的正典連法：在點集的所有三角剖分中，它把三角形弄得盡可能「胖」且勻稱。它是網格的黃金標準，也是沃羅諾伊圖的幾何雙生子。
其定義規則是空圓（或空外接圓）條件，而且可以手算檢驗。點集的一個三角剖分是德勞內的，若對其中每個三角形而言，通過該三角形三頂點的圓（其外接圓）內部「不」含點集中任何其他點。等價且引人注目的是，德勞內三角剖分正是沃羅諾伊圖的「對偶」：當且僅當兩站點的沃羅諾伊胞共享一段邊界時，用一條邊連接這兩個站點，所得到的三角形網路就是德勞內三角剖分。所以這兩種結構以互補的形式承載相同的資訊——一個依鄰近度鋪滿空間，另一個連接最近鄰——而任一者都能由另一者建出。在它受珍視的性質中，德勞內三角剖分在所有三角剖分裡使最小角最大化，這正是它避開細片的精確意涵。
這使它成為有限元素模擬、由高程取樣建立地形模型、電腦圖學、以及散佈資料內插的預設網格產生器，並可在 n log n 時間內算出。它以沃羅諾伊的學生鮑里斯．德勞內（Boris Delaunay）命名，並從那份對偶性繼承了它的優雅。兩個誠實的提醒：第一，唯有當沒有四個點共圓時，三角剖分才唯一——當有四點共圓時（如正方形四角這類「退化」位形），便出現平手，存在不只一個有效的德勞內三角剖分。第二，雖然它使最小角最大化，它並「不」使總邊長最小化、也不保證每個三角形都漂亮；它是依一個特定、精選的判準為最佳，而非同時依所有判準為最佳。
四個點構成一個瘦長的矩形。你可以用兩種方式把它切成兩個三角形：沿一條對角線或另一條。德勞內的選擇是讓每個三角形的外接圓都不含第四點的那條對角線，在此即「較短」的對角線——它產出較胖、最小角較大的三角形，避開了長對角線會造成的細片。若四點反而恰好落在一個圓上（正方形），兩條對角線平手，任一種三角剖分都是德勞內的。
選那條使其三角形外接圓為空的對角線；那就是德勞內翻轉，它把三角形變胖。
德勞內使最小角最大化，但那是它唯一的最佳性保證——它並不使總邊長最小化，而當四點共圓時三角剖分甚至不唯一。