一个平面德劳内三角化的例子,所有三角形外接圆以灰色表示。

数学计算几何 领域, 平面上的点集 P德劳内三角化 是一种 三角剖分 DT(P),使得在 P 中没有点严格处于 DT(P) 中任意一个三角形 外接圆 的内部。Delaunay 三角化 最大化了此三角剖分中三角形的最小角,换句话,此算法尽量避免出现“极瘦”的三角形。 此算法命名来源于鲍里斯·德劳内英语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