资源描述：
《几个多面体网格剖分问题的NP难度证明.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、,一朋,,,,阴彻卜。碑。一巴”抽陀’几个多面体网格剖分问题的难度证明十,田延军邓俊辉清华大学计算机科学与技术系,北京一、恤一,一哪比,,,能恤一一,一一,·目,一阴卜,,,一可一一,一,,一一摘要主要讨论了两类多面体网格剖分问题一一网格表面单调剖分和地形多面体剖分首先研究了判定一个多面体表面能否被刹分成个单调片的问题,通过构造与,问题相应的几何模型证明出该,定,而与之对应的最优剖分问题面体剖分的问题将问题是完全的是的然后将证明方法推广到地形多一个带,洞多面体或者简单多面体刹分成最小数童的地形多面体这两个问题都被证明是的关钮词网格分单调
2、片地形多面体完全中图法分类号文献标识码三维多面体网格剖分简称网格剖分是指按照一定的几何拓扑特征,将三维多面体网格模型或者模型的表、,面分割成一组数量有限的各自具有简单形状意义的子多面体或子分割片的工作近年来网格剖分算法在计算几何、计算机图形学、模式识别和计算机辅助设计等多个领域内都得到了越来越多的研究和应用认知,“心理学认为人类对物体形状进行识别时部分地基于分割”复杂物体往往被看作是简单的基本元素或者组件,,,〔’的组合川由于剖分出来的子模型更加简单也更易于计算机的处理和绘制因此网格剖分被广泛地应用于几、、一,,,和,何变形卜碰撞检测卜
3、纹理映射网格简化等多个问题中三维多面体网格剖分问题主要分为两类一类称为实体剖分,指的是将三维多面体本身分割成多个子多面体另外一类称为表面剖分,指的是将三维多面体的表面分割成多·一一国家自然科学基金一一一一田延军等几个多面体网格剖分问题的难度证明个子分割片一早在年,就证明了三维多面体的最小凸剖分问题是的证明了对一个含有个顶点的多面体进行,,而且在最坏情况下,这个下界是紧的这就凸剖分剖分结果将会得到矛个凸多面体使得实体剖分算法的实际应用价值受到了很大的限制,而且在实际应用中往往不需要去直接分割多面体,因此,网格表面剖分问题就得到了很多研究人
4、员的重视由于实体剖分算法存在着局限性,实际应用中往往只需要将多面体的边界多边形网格表面一一分割,,’】证明了一个非常—重要的结论包含个为不同的子分割片称为网格表面剖分年等人凹边的多面体,表面可剖分为卜个凸的分割片,且给出了一个复杂度为的剖分算法相对于实体凸剖分的平方量级结果来说,该结论表明,网格表面凸剖分的结果是线性的,而且独立于多面体顶点数可见,表面凸剖分更加具有实用价值,同时也证明了多面体表面的最小凸剖分问题仍然是完全的值得一提的是,文献』的证明过程中所剖分出来的每一凸分割片相对于平面都是单调的因此,网格表面单调剖分算法也具有相同的
5、结果,剖分所得到的单调片的个数也是线性的,而且不多于卜所以,网格表面单调剖分算法也同样具有很好的应用价值但是,目前关于单调剖分算法的研究和应用还很少,等人利用,一个启发式的单调剖分算法和图形硬件来加速碰撞检测算法实现简单而且快速达到实时相对于这些结果,本文将证明以下几个问题的难度帅将一个多面体的表面剖分成最小数量的单调片触判定一个多面体的表面能否被剖分成个单调片哪将一个多面体剖分成最小数量的地形多面体哪判定一个多面体能否被剖分成无个地形多面体,一本文第节给出一些基本概念的定义第节证明是完全问题问题是的第节讨论地形多面体的剖分问题,证明对
6、于带洞的多面体或者简单多面体,是完全问题,问题是一的最后在第节进行总结并且讨论几个仍未解决的问题基本概念在多项式时间内,由确定型图灵机,简称可以解决的问题称为尸类问题如,,果一个问题其解法在多项式时间内可以由一个非确定型图灵机简称,,一实现那么此问题属于类问题如果所有的类问题都可多项式规约为问题爪则称刀为难题一,同时,一如果某个问题是的又是问题那么称其为完全困,简称问题是,在算法设计和分析过程中,如果类中最难的一类问题完全性理论的研究在实践中有着重要的指导作用已证明某问题是完全的,这就意味着面临的是一个难于处理的问题对于它,要找出一个在
7、计算机上可行的即多项式时间的算法是十分困难的,甚至可能根本找不到因此,对于完全问题,最好是去寻找近似解法,或者针对该问题的某些有实用价值的特殊情况,寻找多项式时间算法关于图灵机和完全性理论的进一步介绍可参见文献〕下面给出几个与表面剖分相关的重要概念的定义和两个观察结论凹边电多面体尸的一条边,与相关的两个面片所成内角大于分割片印由多面体尸的一个或多个面片及其相关联的顶点和边所构成的集合分割片可以是连通的或者不连通的,,凸分割片多面体尸。。的一个分割片被称为凸的当且仅当完全位于其凸包拭句的边界上且口相对于的每一面片尹和口双句都位于同侧单氏,
8、调对于一个分割片如果平行于方向的任意一条直线与时目交于至多一个点则称时目对于是单调的如果口上各点到平面二的垂直投影互不相同,则称时兀目对于是单调的单调片对于一个分割片氏如果存在一个方向,伏,使得时目对于是单
