几个多面体网格剖分问题的np难度证明

主要讨论了两类多面体网格剖分问题——网格表面单调剖分和地形多面体剖分.首先研究了判定一个多面体表面能否被剖分成k个单调片的问题,通过构造与sat问题(satisfiabilityproblem)相应的几何模型,证明出该判定问题是np完全的,而与之对应的最优剖分问题是np-hard的.然后将证明方法推广到地形多面体剖分的问题:将一个带洞多面体或者简单多面体剖分成最小数量的地形多面体,这两个问题都被证明是np-hard的.