德洛奈三角剖分（Delaunay triangulation）是1934年由俄国数学家B.德洛奈（Boris Delaunay）提出。在点集可能形成的三角剖分中，德洛奈三角剖分所形成的三角形的最小角最大。即德洛奈三角剖分能避免出现“极瘦角”。给定一个点集，如果所有点共线，则不存在德洛奈三角剖分；若有至少四点共圆，则德洛奈三角剖分不唯一。

最简单的德洛奈三角剖分算法是翻边算法。但是这个算法的时间复杂度是O(n²)。Lawson提出了逐点插入和局部优化的算法，Bowyer和Watson在1981年也提出总体思路为逐点插入的算法，时间复杂度也较高。分治法最初由Lee和Schachter提出，然后由Guibas和Stolfi改进，最终由Dwyer完善，时间复杂度为O(nlogn)。

德洛奈三角剖分可以推广到高维空间（维度大于等于3），甚至其他度量空间（非欧空间；此时德洛奈三角剖分并不能保证存在或者唯一）。

①一个点集是规则化的（即点集内任意四点不共圆）当且仅当该点集上的德洛奈三角剖分是唯一的。

②D(P)为点集的德洛奈三角剖分当且仅当其中任意三角形的外接圆内部不含P中的点。

③能最大化点集P的三角剖分中三角形的最小角的三角剖分是德洛奈三角剖分。任意P上的德洛奈三角剖分都能最大化P上所有三角剖分的最小角。

④德洛奈三角剖分最外层的边界形成一个凸多边形的外壳。

⑤不论从区域何处开始构建德洛奈三角剖分，最终都将得到一致的结果。

⑥德洛奈三角剖分中任意两个相邻三角形形成的凸四边形的对角线如果可以互换的话，那么两个三角形六个内角中最小的角度不会变大。

图1　虚线部分是给定点集的维诺图，实线部分是维诺图的对偶图。

图2　将图1中对偶图的曲线拉直得到德劳内图

图1中的虚线部分是给定点集的维诺图，实线部分是维诺图的对偶图。将对偶图的曲线拉直，就可得到德洛奈图（图2）。向德洛奈图中添加边所得到的三角剖即可得到德洛奈三角剖分。

构建给定点集的任意三角剖分，翻转由两个共边的相邻三角形所形成的凸四边形的两个对角边线，使得没有三角形是非德洛奈的（即三角形的外接圆含P中的点）。这个算法简单，但是时间复杂度较高。

构造一个大三角形，包含点集P；依次随机插入点集中的点，去掉外接圆包含插入点的三角形，留出一个星形空洞，连接插入点和空洞边上的点，重新剖分；移除第一步中插入的三个点及其所在的三角形即得结果。

主要思路是递归分割点集，到点很少的时候（比如3个），这个德洛奈剖分就是三点连线。然后把剖分结果沿分隔线合起来。

高维空间内的点集P的德洛奈三角剖分定义为使得在中没有点严格处于D(P)中任意一个单形外接超球面的内部的三角剖分。

高维空间（例如d维）点集的德洛奈三角剖分问题可以转化为求点集在d+1维上的凸包问题（给每个点p增加一个维度的坐标，值取为|p|²）。然后将凸包映射回原来的维空间。

德洛奈三角剖分在数学分析、科学计算、有限元方法、图形学、地质学等领域都有广泛的应用。①在地形建模或者其他用点表示的模型中，德洛奈三角剖分可以生成十分实用的三角网模型。尤其德洛奈三角剖分可以最大化最小角，能避免模型中“极瘦角”的出现。②通过德洛奈曲面细分估计法，德洛奈三角剖分可以用于检测样本点集的密度或者强度。③德洛奈三角剖分算法的时效性和最大化最小角的性质，使得它经常可以用于构建空间三角网格，例如用于有限元分析和有线体积法。④约束德洛奈三角剖分算法可用于自动驾驶中的路径规划。