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

来源 :软件学报 | 被引量 : 7次 | 上传用户：lixinlixin2008

【摘要】

：

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

【作者】

：

田延军邓俊辉

【机构】

：

清华大学计算机科学与技术系

【出处】

：

软件学报

【发表日期】

：

2008年04期

【关键词】

：

网格剖分单调片地形多面体 NP完全 mesh decomposition monotone patch terrain polyhedron NP-c

【基金项目】

：

Supported by the National Natural Science Foundation of China under Grant No.69803006 （国家自然科学基金）

下载到本地 , 更方便阅读

下载此文赞助VIP

声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架

论文部分内容阅读

其他文献

无线Ad Hoc网络中基于时间广播的功率感知路由

提出了一种TBPR（time．based broadcasting for power-aware routing）协议．TBPR采用路由请求报文延迟发送机制，并通过比较路径中的累计功率消耗，选择能量消耗较低的路由，以降低网络的

期刊

基于时间广播功率感知等待时间累计功率无线ADHOC网络timer-based broadcasting power-aware waiting t

检测微小RNA-126对于评判小细胞肺癌预后的临床价值

目的明确检测微小RNA-126对于评判小细胞肺癌（SCLC）预后的临床价值.方法纳入我院收治的SCLC患者,并进行为期12个月的随访以确认预后,比较不同预后患者组间各项指标的差异性;

期刊

微小RNA-126小细胞性肺癌肿瘤标志物microRNA-126 small cell lung cancer tumor markers

条纹坚固呢的开发浅议

<正>一、条纹坚固呢的风格特征条纹坚固呢一般采用纯棉、麻棉等天然纤维,它保持了天然纤维吸湿性强,透气性好、穿着舒适的优点。经高级整理可获得防皱,防缩、防变形的特殊

期刊

条纹坚固呢棉纤维混纺纱织造

小潮气量通气对ALI／ARDS高风险患者疗效及预后的影响分析

目的研究机械通气治疗的急性肺损伤/急性呼吸窘迫综合症(ALI/ARDS)高风险患者,应用小潮气量通气对患者疗效和预后的影响。方法采用随机数字表法将本院重症监护病房(ICU)收治

期刊

机械通气急性肺损伤急性呼吸窘迫综合症小潮气量通气

络筒工艺接头方式的选择

<正> 一、络筒工序接头的目的络纱时遇到纱线断头或管纱用完时,必须打结,使前后连接起来。接头在整个络纱工作中,占有很大的比重,是提高络筒和织造产、质量的重要环节之一。

期刊

织造工艺络纱接头方式选择

高产奶牛饲养技术推广机制与模式选择

黑龙江省是典型的农业大省,地处世界黄金玉米带和黄金奶牛带,奶牛饲养具有得天独厚的条件。奶牛的产奶量除了与环境、品种等有关外,主要在于采用科学的技术规范进行标准化饲

期刊

高产奶牛饲养技术推广机制

内黄县驻路办公模式经济效益分析

创新依法治路模式是贯彻落实科学发展观及提升公路经济效益的必然要求,在依法创新治路模式中必须强化路政管理,加快驻路办公建设,切实将战略任务落到实处,只有这样才能使中国

期刊

治路模式公路工程经济效益创新

论广告市场准入制度

广告市场准入制度是指对广告经营者的审批登记制度，应通过在企业资本、知识、技术和人才等方面提高准入门槛，可以减少不必要的恶性竞争，提高广告行业的档次和质量，向知识型、技术

期刊

广告市场准入制度广告经营者广告设计制作企业

基于政府层面的安徽品牌建设思考

实施品牌建设是一项复杂的系统工程，实施品牌建设的措施是：加强品牌建设的基础工作；建设品牌服务的支撑体系；完善激励机制；加强对品牌的保护；做好宣传工作；加强对品牌建设工作的领导

期刊

品牌建设必要性内涵内容措施brand building： necessity connotation contentmeasures

基于虚拟势场的有向传感器网络覆盖增强算法

首先从视频传感器节点方向性感知特性出发，设计了一种方向可调感知模型，并以此为基础对有向传感器网络覆盖增强问题进行分析与定义：其次，提出了一种基于虚拟势场的有向传感器网络

期刊

有向传感器网络有向感知模型虚拟势场覆盖增强directional sensor network directional sensing model

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

与本文相关的学术论文