%0 Journal Article
%T 几个多面体网格剖分问题的np难度证明
%A 田延军？
%A 邓俊辉？
%J 软件学报
%P 1026-1035
%D 2008
%X 主要讨论了两类多面体网格剖分问题——网格表面单调剖分和地形多面体剖分.首先研究了判定一个多面体表面能否被剖分成k个单调片的问题,通过构造与sat问题(satisfiabilityproblem)相应的几何模型,证明出该判定问题是np完全的,而与之对应的最优剖分问题是np-hard的.然后将证明方法推广到地形多面体剖分的问题:将一个带洞多面体或者简单多面体剖分成最小数量的地形多面体,这两个问题都被证明是np-hard的.
%K 网格剖分
%K 单调片
%K 地形多面体
%K np完全
%U http://www.jos.org.cn/ch/reader/view_abstract.aspx?file_no=20080420&flag=1