amath

三维凸包

Felicia

Mar 28, 2008

1 三维凸包的复杂度

定理 1
设`P`为包含`n`个顶点的任意凸多面体。则`P`中所含的边不会超过`3n – 6`条，所含的面不会超过`2n – 4`张。
证明：该凸多面体`P`可看做平面图。在与`P`对应的图中，每张面都是至少由`3`条边围成的，而且每条边都与两张面相关。因此我们得到`2n_(e) <= 3n_(f)`。代入欧拉公式`n - n_(e) + n_(f) = 2`，得到：`n + n_(f) -2 <= 3n_(f) / 2`。于是有`n_(f) <= 2n - 4`，再代入欧拉公式得到`n_(e) <= 3n - 6`。

因此我们有如下结论：
推论 1
`n`个点的三维凸包的边数为`O(n)`，面数为`O(n)`。

2 三维凸包的算法

计算三维凸包的算法有很多种，包括：随机增量法，卷包裹法，Graham扫描法等。其中随机增量法实现起来很简单，尤其适合信息学竞赛的应用。下面给出随机增量算法：

1. 在`P`中找出4个不共面的点`p_1,p_2,p_3,p_4`，构成一个四面体，作为初始凸包。
2. 将其余各点随机排列，按照以下规则加入凸包（假设加入的点是`p`）：
   1. 将凸包看作实体，确定从`p`能够看到的面。
   2. `p`的可见面与不可见面的交界称为地平线，将`p`与地平线上的每个点连接，生成若干个新的面。
   3. 删去原先从`p`可见的面。

3 随机增量算法的演示程序

endamath