Ref1002

在计算几何中，沃洛诺伊图（Voronoi Diagram）和德劳内三角（Delaunay Triangulation）的数量关系是固定的，并且可以通过欧拉公式和对偶性推导出来。

假设我们有一组 $n$n 个点（种子点），并且这些点处于一般位置（没有三点共线，没有四点共圆，也没有两个点拥有完全相同的 $x$x 或 $y$y 坐标），那么它们之间的数量关系如下：

1. 核心对应关系

• 德劳内三角的顶点数 $V_d$Vd​ = $n$n（即原始种子点的数量）。
• 沃洛诺伊图的顶点数 $V_v$Vv​ = 德劳内三角形的外心数量。
• 沃洛诺伊图的边数 $E_v$Ev​ = 德劳内三角的边数 $E_d$Ed​。
• 沃洛诺伊图的面数 $F_v$Fv​ = 德劳内三角的顶点数 $V_d$Vd​ = $n$n。

2. 精确的数学表达式

对于 $n$n 个点（假设 $n\ge 3$n≥3）：

德劳内三角

• 顶点数 VdVd​： $n$n
• 三角形数量 FdFd​（即三角剖分中的面数）： 在凸包边界固定的情况下，最大为 $2n-2-h$2n−2−h，其中 $h$h 是凸包上的顶点数。当所有点都在凸包上（$h=n$h=n）时，三角形数量为 $2n-2-n=n-2$2n−2−n=n−2（即凸多边形三角剖分）；当点集包含内部点时，三角形数量会增加。
  • 更通用的公式是：T=2n−2−hT=2n−2−h，其中 $T$T 是德劳内三角形的个数，$h$h 是凸包上的顶点数。
• 边数 EdEd​： $3n-3-h$3n−3−h

沃洛诺伊图

• 面数 FvFv​： $n$n（每个种子点对应一个面）。
• 顶点数 VvVv​：$2n-2-h$2n−2−h
  • 解释： 这个数正好等于德劳内三角形的个数。因为每个德劳内三角形的外心对应一个沃洛诺伊顶点。对于平面上的 $n$n 个点，其德劳内三角剖分中三角形的数量就是 $2n-2-h$2n−2−h，所以沃洛诺伊顶点数也是这么多。
• 边数 EvEv​：$3n-3-h$3n−3−h
  • 解释： 沃洛诺伊边数与德劳内边数相同。每一条德劳内边对应一条沃洛诺伊边（垂直平分线）。不过需要注意的是，沃洛诺伊图中有些边是射线（通向无穷远），但在计数时通常算作一条边。

3. 举例说明

假设有 $n=10$n=10 个点，且凸包上有 $h=5$h=5 个点：

• 德劳内三角：
  • 顶点：10
  • 三角形：$2\ast 10-2-5=20-7=13$2∗10−2−5=20−7=13
  • 边：$3\ast 10-3-5=30-8=22$3∗10−3−5=30−8=22
• 沃洛诺伊图：
  • 面：10
  • 顶点：$13$13（与三角形数量相同）
  • 边：$22$22（与德劳内边数相同）

4. 特殊情况：退化情况（四点共圆）

如果出现退化情况（例如四个点共圆），沃洛诺伊图会出现一个顶点连接四条边的情况。此时，德劳内三角剖分不唯一（可以有多种画法连接这些点）。

在退化情况下，上述数量关系会发生变化，但沃洛诺伊图的顶点数仍然等于德劳内三角中不重复的外心数量。

总结对照表

项目	沃洛诺伊图	德劳内三角
顶点数	2n−2−h2n−2−h（即三角形数量）	nn（即种子点数量）
边数	3n−3−h3n−3−h	3n−3−h3n−3−h
面数	nn	2n−2−h2n−2−h（即三角形数量）

(注：nn 为总点数，hh 为凸包上的顶点数)