# Voronoi 图复杂度的欧拉公式证明

我们希望证明：对于 $n > 2$ 个点的 Voronoi 图 $V(P)$，其复杂度是线性的：

• 顶点数 $\leq 2n - 5$
• 边数 $\leq 3n - 6$

# 📐 使用欧拉公式

欧拉公式是平面图中的基本定理：

$$V - E + F = 2$$

其中：

• $V$ 是顶点数
• $E$ 是边数
• $F$ 是面数（Voronoi cell 数量，即原始点数 $n$）

# 🔧 添加虚拟点使图封闭

由于 Voronoi 图的某些边是无穷延伸的半线，不能直接套用欧拉公式。为了解决这个问题，我们：

• 添加一个虚拟点 $v$
• 将所有半线连到 $v$，使图成为封闭图

这样我们有一个新的图，满足欧拉公式：

$$(V + 1) - E + n = 2 \quad \text{（记作 *）}$$

# 🔁 顶点度数下界

Voronoi 图中的每个顶点（包括新增的 $v$）至少有 度数为 3，因为：

• 一个 Voronoi 顶点是三个 Voronoi cell 的交点
• 所以它至少连接三条边

因此：

• 所有顶点度数之和 $\geq 3(V + 1)$
• 而总度数也等于 $2E$

所以：

$$2E \geq 3(V + 1) \Rightarrow V \leq \frac{2}{3}E - 1$$

# 🔚 代入欧拉公式

将上式代入公式 (*)：

$$\left(\frac{2}{3}E - 1 + 1\right) - E + n = 2 \\ \Rightarrow \frac{2}{3}E - E + n = 2 \\ \Rightarrow -\frac{1}{3}E = 2 - n \\ \Rightarrow E = 3n - 6$$

再代入 $V \leq \frac{2}{3}E - 1$ 得：

$$V \leq \frac{2}{3}(3n - 6) - 1 = 2n - 5$$

# ✅ 结论

• 边数 $E \leq 3n - 6$
• 顶点数 $V \leq 2n - 5$
• Voronoi 图总结构复杂度为 $O(n)$（线性）

# 握手引理 (hand shake)

![[Pasted image 20250612183042.png]]

# 需要补充的内容

加入 NP BBP... 具体指的是什么

![[Pasted image 20250617174412.png]]