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

第1卷第3期2006 年10 月191 中国科技论文在线 SCIENCEPAPER ONLINE 凸多边形的闵可夫斯基和分解及其最优估计 张松海,吴奕(清华大学计算机科学与技术系,北京 100084) 摘要:本文讨论了闵可夫斯基和的逆问题(称为闵可夫斯基和分解) ,即将一个凸多边形分解为两个更为简 单的凸多边形的问题, 首先通过三角分解的方法证明了凸多边形闵可夫斯基和分解的存在性, 在此基础上研究 了在边个数和面积之和的意义下的最优分解.

关键词:闵可夫斯基和分解;

凸多边形;

三角分解 中图分类号:TP391 文献标识码:A 文章编号:1673-7180(2006)03-0191-6

0 引言 闵可夫斯基和是计算几何中的基本运算, 对于 A 和B两个集合,闵可夫斯基和? 定义为 A? B={α +b|α∈A,b∈B} ,两个凸多边形的闵可夫斯基和 的时间复杂度是 ( ) O m n + .它广泛应用在机器人学 中的碰撞检测[1] ,数据压缩和 CAD 等各个方面.闵 可夫斯基和在分析几何的容差问题的时候也起到了 重要的作用,由于使用凸多边形表示误差区域,并 且基于最坏情况法对误差进行估计,所以误差区域 的大小主要是利用闵可夫斯基和进行计算[2][3] ,并且 许多几何变换的误差域可以直接通过凸多边形的闵 可夫和来计算求得的[4] ,对于 Bézier 和B样条曲线 误差域的计算,最终也可以归结为各控制顶点误差 域的线性组合.然而对于该问题的反问题,即已知 几何变换后允许的最大误差域,来估计输入的胖点 的误差域的问题还没有得到很好的研究.通过把误 差域凸多边形做闵可夫斯基和分解成子多边形,可 以帮助解决这个问题,这也是本文的出发点之一. 本文主要研究闵可夫斯基和的逆过程,即对一 个给定的凸多边形,将其分解为两个更为简单的凸 多边形,并研究那些使得分解的两个子多边形的总 边数和或者总面积和最小的最优分解,从而为误差 控制提供理论基础. Rolf Schneider[5] 证明了在二维平 面上,只有三角形和线段是不可分解的,即所有的 平面凸多边形 P,都存在多边形 M 和N, 使得 P=M+N.而本文给出更强的结论,我们将证明任何 凸(5) N N≥ 边形的非平凡二分解不仅一定存在, 而且 一定能找到一种所谓的三角分解,即所得到的分解 中有一个元素是三角形的分解.本文还将依次探讨 多边形在边个数最小和面积最小的两种最优情况下 的闵可夫斯基和分解,并给出相关的算法.

1 闵可夫斯基和分解的存在性及其三角分解 定义 1:对于一个凸多边形 P, 定义表示 S(P)为 多边形 P 的边数和. 定理 1:若一个凸多边形 P 可以表示为若干个 凸多边形的闵可夫斯基和,即1niPPi = = ∑ , 则1()()niSPSPi = ≤ ∑ . 证明:因为 P 的每一条边必然都是由子多边形 中若干条与其方向相同的边叠加而成. 由于P有S(P) 条边,那么,所有的 Pi 中至少也应该有 S(P)条边. 即1()()niSPSPi = ≤ ∑ , 证毕. 从定理

1 的证明中我们可以看出当我们把一个 凸N边形 P,分解成两个子多边形 P1和P2的时候, 必然有

1 2 ( ) ( S P S P N + ≤ ) ,因此如果一个凸多边形能 够分解成两个多边形,使得这两个子多边形的边数 之和为原多边形的边数,那么该分解一定是边数意 义上的最优分解. 基金项目:国家自然科学基金( 60273012). 作者简介:张松海(1978-),男,博士研究生,主要研究方向为计算机辅助几何设计、计算机图形学. 第1卷第3期2006 年10 月192 定义 2: 如果三个m1, m2, m3 向量形成如图