背景
对于任意多边形我们总能将其划分成若干三角形组成，比如一个四边形可以划分成两个三角形，一个六边形可以划分成四个三角形。将多边形划分成若干三角形称为三角剖分。一个多边形有许多种三角剖分的方案，其中有一种三角剖分称为Delaunay三角剖分。Delaunay三角剖分具有这些性质：
(1) Delaunay三角剖分所形成的三角形中，最小的内角是所有三角剖分中最大的。这个性质表明，Delaunay三角剖分将多边形分解成若干三角形，且这些三角形尽量都接近于等边三角形，这个性质在许多问题都有很大的应用。
(2) Delaunay三角剖分所形成的三角形，所有三角形的外接圆都不包含其他顶点，即任意四点不共圆，也叫空圆性质。这一性质保证了Delaunay三角剖分只有一种。
(3) 在一个Delaunay三角剖分中加入一个新的顶点，只需要删除所有外接圆包括新顶点的三角形，并连接新顶点与以该顶点为中心的多边形的各顶点，可以证明此时的三角剖分是加入新顶点后的点集的Delaunay三角剖分。
算法
Delaunay三角剖分最经典使用最多的方法是增量法，利用到前面提到的第三个性质，主要有以下步骤：
(1) 生成一个包含所有点的大三角形
(2) 每次加入一个新顶点，去掉包含该顶点的外接圆的三角形，将该顶点与以该顶点为中心的多边形的各顶点连接
(3) 重复步骤2，直到加入点集所有点，将与初始大三角形相关的边去除，得到Delaunay三角剖分
上述算法有一个优化的关键就是快速找到包含新顶点的外接圆的三角形，方法是初始时将所有点加入到大三角形，然后每次划分出新的三角剖分时，更新各个点集中各个点的归属，更新各个三角形中包含的点，比如将一个大三角形分成三个新的小三角形，则重新计算这个大三角形中的点的归属，将这些点具体归入到三个新的小三角形。在随机情况下，时间复杂度是$O(n\log n)$。
应用
Delaunay三角剖分可以用于求二维平面点集最短距离点对或二维平面不同点集最短距离点对等等，最短距离点对包含在Delaunay三角剖分的某条边。
参考
https://blog.csdn.net/ganbaoni9yang/article/details/50034065