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

• 作者: 田延军 邓俊辉
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 网格剖分 单调片 地形多面体 NP完全
• 年，卷（期）: 2008,（4）
• 所属期刊栏目: 计算机图形学与计算机辅助设计
• 页码范围: 1026-1035
• 页数: 10页
• 分类号: TP391
• 字数: 5144字
• 语种: 中文
• DOI: 10.3724/SP.J.1001.2008.01026

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	邓俊辉	清华大学计算机科学与技术系	17	376	8.0	17.0
2	田延军	清华大学计算机科学与技术系	1	4	1.0	1.0