| 摘要: |
| 主要讨论了两类多面体网格剖分问题——网格表面单调剖分和地形多面体剖分.首先研究了判定一个多面体表面能否被剖分成k个单调片的问题,通过构造与SAT问题(satisfiability problem)相应的几何模型,证明出该判定问题是NP完全的,而与之对应的最优剖分问题是NP-hard的.然后将证明方法推广到地形多面体剖分的问题:将一个带洞多面体或者简单多面体剖分成最小数量的地形多面体,这两个问题都被证明是NP-hard的. |
| 关键词: 网格剖分 单调片 地形多面体 NP完全 |
| DOI： |
| 分类号: |
| 基金项目:Supported by the National Natural Science Foundation of China under Grant No.69803006 (国家自然科学基金) |
|
| NP-Hardness of Some Polyhedral Mesh Decomposition Problems |
|
TIAN Yan-Jun,DENG Jun-Hui
|
| Abstract: |
| This paper considers the problem of decomposing a polyhedral surface or a polyhedron into simpler components: Monotone patches or terrain polyhedra. It is shown to be NP-complete to decide if a polyhedral surface can be decomposed into k monotone patches, by constructing a geometric model to make a reduction from SAT (satisfiability) problem. And the corresponding optimization problem is shown to be NP-hard. Then, the method is extended to the problems of decomposing a polyhedron with or without holes into the minimum number of terrain polyhedra, both of which are also shown to be NP-hard. |
| Key words: mesh decomposition monotone patch terrain polyhedron NP-complete |
