PDF《凸多边形的闵可夫斯基和分解及其最优估计》

1 (a) 的位置, 亦即m1 到m2, m2 到m3, m3 到m1 的夹角都在

0 到180 度之间,则称m1,m2,m3 为可三角化的, 而图 1(b)的三个向量就是不可三角化的,因为m3 到m1 的角大于

180 度.

1 m

2 m

3 m (a)

1 m

2 m

3 m (b) 图1向量三角化 定理 2: 任意一个凸 ( 6) n n ≥ 边形都可以分解成 为一个一个三角形和一个凸 m 边形的闵可夫斯基 和,其中 3, 2,

1 m n n n 为证明该定理,我们先证明一个引理. 引理 a:对于任意

6 n ≥ 个方向各不相同的二维 向量,如果它们的和为零,必定可以从中选出三个 向量,使得它们可三角化. 证明:我们用反证法进行证明.取这 n 个向量 中的两个向量 , a b, 使得这两个向量的夹角α是所有 在(0,π)中的夹角最大的向量对,设,ab的位置如 图2所示: a b c d

2 1

3 4 图2引理 a 证明图 我们可以看到,区域

1 和区域

3 中就不可能有 其他向量了,否则与α的最大性矛盾.如果在区域

4 中存在向量 e ,那么向量 , , a b e 即为满足要求的可三 角化的三个向量.所以区域

4 中不存在向量,那么 所有不在 , a b 之间的向量只有可能在 , c d 方向上, 此时若 , c d 方向上只有一个有向量,不妨设为 d 方向,则考虑这 n 个向量在 d 方向的投影,必定不为 零,与题设矛盾;

所以 , c d 方向上都应存在向量, 因为向量总条数大于 4,所以除了 , , , a b c d 四个向 量以外必定至少还有一个向量 f ,且由于该向量不 可能在区域

1、3 和4,那么它必然在区域 2,那么 , , c d f 为满足要求的三个可三角化的向量.证毕. 有了以上的引理, 下面我们来证明定理 2, 把凸 多边形的n条边看作n个首尾相连的向量,显然

1 2 3...

0 n a a a a 由引理,必然存在如图

3 形式的三个向量

1 2

3 , , a a a 可以三角化.

1 a

2 a

3 a α β χ 图3定理

2 证明图 如果设

3 2

1 3

2 1

1 2

3 , , , min( , , ) sin sin sin a a a r r r r r r r χ β α = = = = , 由正弦定理有

1 2

3 1

2 3

0 r r r a a a r r r + + = 并且

1 2

3 1

2 3 , , r r r a a a r r r 可以构成一个三角形,它 的三个内角分别为α β χ , , .这个三角形就是我们 要求的闵可夫斯基和分解成的两个多边形中的一个 三角形, 由于边数之和大于等于 6, 所以去掉这个三 角形的三条边,至少还剩下

3 条边,于是组成另一 个多边形的边向量应该为

1 2

3 4

1 2

3 (1 ) ,(1 ) ,(1 ) , , n r r r a a a a a r r r ? ? ? LL .因为有

1 2

1 2

3 1

2 3 ....

0 0 n a a a r r r a a a r r r + + = + + = 我们可以得到

1 2

3 4

1 2

3 (1 ) (1 ) (1 )

0 n r r r a a a a a r r r LL 可以看出,剩下的边能够组成一个凸多边形. 该多边形的边数取决于系数

1 2

3 (1 ) (1 ) (1 ) r r r r r r ? ? ? , , 中等 于0的个数.若其中有 k 个为零,则多边形是 n-k 凸多边形的闵可夫斯基和分解及其最优估计 第1卷第3期2006 年10 月193 中国科技论文在线 SCIENCEPAPER ONLINE 边形,显然有 k=1,2,3,由此证明了定理 2. 定理

2 推论:任意一个凸五边形也可以分解成 一个三角形和一个凸四边形或三角形的闵可夫斯基 和的形式. 证明:类似于定理

2 的证明过程,唯一不同的 是有可能

1 2

3 (1 ) (1 ) (1 ) r r r r r r ? ? ? , , 中有三个为零的情况,则 此时这个凸五边形必然是如下的形状.

1 a

2 a

3 a

4 a

5 a 图4推论证明图 其中123,,