德劳内三角剖分

德劳内三角剖分（Delaunay triangulation）用站点作为顶点，把平面点集的凸包剖成三角形，并要求每个三角形的外接圆内部没有其他站点。这里的“空”限制圆的内部，三角形自己的三个顶点当然在圆周上。它把最近邻几何、空圆条件和三维凸包联系起来。

空圆筛掉一条对角线

取凸四边形 $A=(0,0),B=(4,0),C=(4,3),D=(0,2)$。沿 AC 剖分时，三角形 ABC 的外心为 $(2,3/2)$，半径平方为 $25/4$。D 到该外心的距离平方只有 $17/4$，严格小于半径平方。因此 D 落在外接圆内部，AC 这条剖分对角线不合格。

检验的是三角形的整个外接圆盘，不能只检查三角形内部。D 虽在 ABC 外部，仍破坏空圆条件。

换成 BD 后，三角形 ABD 的外心为 $(2,1)$、半径平方为五，剩余点 C 的距离平方为八，位于圆外。三角形 BCD 的外心为 $(9/4,3/2)$、半径平方为 $85/16$；剩余点 A 的距离平方为 $117/16$，也在圆外。四点只有这两种剖分，故 BD 给出唯一的德劳内三角剖分。

两个圆盘可以相交；要求是各自内部都不含任何其他站点。

对象、一般位置与沃罗诺伊对偶

以下先假设有限点集至少含三个点，点两两不同，没有三点共线，也没有四点共圆。三角剖分覆盖点集凸包，边只在公共端点相交，每个点都用作顶点。满足空圆条件的剖分存在且唯一。沃罗诺伊图中两单元共享一条边时，连接它们的站点，就得到德劳内边；三个单元相遇的顶点是对应三角形的外心。

对偶的空圆含义可以直接核验：沃罗诺伊边上的点 c 到两站点 p、q 等距，且没有其他站点更近，故以 c 为圆心、该距离为半径的圆内部为空。反过来，若存在经过 p、q 且没有其他站点位于圆盘内部或圆周上的圆，那么圆心附近沿 pq 垂直平分线的一小段仍以 p、q 为最近站点，于是两单元共享边。在一般位置下，即使最初的空圆还经过第三点，也可沿相应单元边取得只有两站点在圆周上的圆。共圆退化时，不能把仅在一个沃罗诺伊顶点相遇的任意两单元都当成共享边。

空圆与下凸包的完整对应

把平面点 $p=(p_x,p_y)$ 提升为三维点 $p^{+}=(p_x,p_y,p_x^2+p_y^2)$，全部位于抛物面 $z=x^2+y^2$ 上。若某三角形的外接圆圆心为 $c=(c_x,c_y)$、半径为 r，三个提升点所在平面为 $$z=2c_{x}x+2c_{y}y+r^2-\Vert c{\Vert }^2.$$ 这是把圆方程 $\Vert p-c{\Vert }^2=r^2$ 展开所得。对任意其他站点 q，它的提升高度减去该平面在 q 上方的高度，恰为 $$\Vert q{\Vert }^2-2c\cdot q-r^2+\Vert c{\Vert }^2=\Vert q-c{\Vert }^2-r^2.$$ 所以 q 在圆内、圆上、圆外，分别等价于提升点在该平面下、平面上、平面上方。因而外接圆内部为空，恰表示该平面下方没有提升站点，即三角形是提升点凸包朝下的面。

下凸包为什么给出剖分也能说明：对凸包中每个平面位置 x，在所有投影为 x 的三维凸组合中取最低高度，所得点构成下表面。这个分段平面的表面投影覆盖原点集凸包；两个不同面的投影内部不能重叠：若在一片二维区域上重叠，两平面都必须给出相同最低高度，便在开集上相等，从而是同一个平面、同一个面。每个站点提升后的切平面只接触自身，因为其他点的高度差为 $\Vert q-p{\Vert }^2>0$，故所有站点都会出现在下表面。无四点共圆保证非竖直下表面没有四个共面站点，所以它的面都是三角形。三个点时直接取唯一三角形即可。

这既证明空圆剖分存在，也证明一般位置下唯一：每个空圆三角形都必须是同一个下凸包的面，不能有另一个不同的三角剖分同时满足条件。

共圆变式与使用边界

若四点改为正方形 $(0,0),(4,0),(4,4),(0,4)$，它们共用外心 $(2,2)$。任选一条对角线，两三角形外接圆内部都不含其他站点，故两种剖分都合格。提升后四点共面，对应下凸包一个四边形面；必须再选一条对角线才能得到三角形。这是非唯一性的具体来源。

若所有站点共线，就没有覆盖二维面积的三角形剖分；重复点、几乎共圆的浮点数据也需显式处理。空圆条件不表示所有三角形都接近正三角形：若输入仅有一个极瘦三角形，唯一剖分仍然极瘦。边界形状和输入分布限制了可改善的程度。这里讨论不带障碍或指定线段的普通点集剖分；带约束线段的网格需要另设规则，不能强迫每条指定边满足同一全局空圆条件。