德勞內三角剖分

在數學和計算幾何領域，平面上的點集P的德勞內三角剖分（英語：Delaunay triangulation）是一種是點P的一個三角剖分DT，使在P中沒有點嚴格處於 DT(P) 中任意一個三角形外接圓的內部。德勞內三角剖分最大化了此三角剖分中三角形的最小角，換句話，此算法儘量避免出現「極瘦」的三角形。此算法命名來源於鮑里斯·德勞內（英語：Boris Delaunay），以紀念他自1934年在此領域的工作。^[1]

一個平面德勞內三角化的例子，所有三角形外接圓以灰色表示。

與沃羅諾伊圖的關係

若一離散點集的點均處於一般位置，則德勞內三角化就對應到沃羅諾伊圖的對偶。特殊情形包括了三點共線及四點共圓

• 
  一個德勞內三角化的例子，所有三角形外接圓的圓心以紅點表示。
• 
  連接外接圓圓心即產生沃羅諾伊圖，在此以紅線表示。

參見

1. B. Delaunay: Sur la sphère vide, Izvestia Akademii Nauk SSSR, Otdelenie Matematicheskikh i Estestvennykh Nauk, 7:793–800, 1934