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

aaa恰好构成了三角形,123450aaaaa 则 ,那么

1 3

5 , , a a a 必然构成三 角形,否则如果此时仍有315242500aaaaaaa ,那么 ,从而 矛盾! 所以可以另取135,,

aaa可三角化,且相应的123(1 ) (1 ) (1 ) r r r r r r ? ? ? , , 中为零的个数k=1或2, 因此原五 边形此可分解成为一个三角形和一个四边形或一个 三角形的闵可夫斯基和的形式.证毕. 通过以上推导我们可以得到任何一个凸 n (

6 n ≥ )边形都可以分解成为一个一个三角形和一个 m 边形的闵可夫斯基和,其中3, 2,

1 m n n n = ? ? ? 或.定义 3:把一个凸 ( 6) n n ≥ 边形分解成为一个一 个三角形和一个凸 m 形的闵可夫斯基和(其中 3, 2,

1 m n n n = ? ? ? 或 )的过程定义为该凸多边形 的三角分解. 定理 3: 任何一个凸多边形都可以不断分解成以 下几种基本图形的闵可夫斯基和:三角形、平行四 边形和梯形. 先证明一个引理. 引理 b:一个不存在平行边的四边形可以分解 成为两个三角形的闵可夫斯基和的形式.

1 3

4 2 图5无平行边四边形的分解 证明: 如图 5,边1,3,4 是可三角化的,且 显然此时分出的另一个图形也是三角形.引理证毕. 定理三的证明:由上面的引理,任何一个凸N 边形都可以不断作三角分解,使之最后成为三角形, 平行四边形,梯形的闵可夫斯基和.并且当分解到 三角形,平行四边形,梯形后已经不再存在非平凡 分解,即分解成更简单的多边形的分解了,这是因 为对于三角形,显然无法再简单了.对于平行四边 形,由于只有两种方向的向量, (把平行的向量看作 一类) ,而要分解成三角形,至少需要三个互不平行 的向量.对于梯形,由于要构成三角形,只能取两 腰和较长的底,但此时所能做的分解只能是分成一 个三角形和一个新的梯形的和(如图 6) ,但是这种 分解没有把梯形分解为更简单(边数更少)的多边 形的闵可夫斯基和. 综上,我们完成了对定理

3 的证明. 图6梯形分解 注记: 定理

3 的结果可以直接推出 Rolf 的结果, Rolf 的结果是不存在非平凡分解的只可能是线段和 三角形,而我们的得到的结果由于不认为线段是一 个平面图形,........