顶点覆盖问题的贪心算法在网格简化中的应用研究  

Applying Greedy Algorithm of Vertex Cover to Mesh Simplification

作　　者：陈慧群[1] 周亮[2] 

机构地区：[1]深圳信息职业技术学院,广东深圳518172 [2]华为技术有限公司,广东深圳518129

出　　处：《深圳信息职业技术学院学报》2012年第1期18-21,共4页Journal of Shenzhen Institute of Information Technology

基　　金：深圳信息职业技术学院青年自然科学基金资助项目(QN-08013)

摘　　要：针对三角网格简化,设计了求解顶点覆盖问题的贪心算法,通过贪心选择最小的顶点集去"覆盖"边集,同时保留被简化网格的特征信息,自动实现最大程度简化。给出的实例也表明简化后的网格质量良好,算法既降低了时间复杂度又保持了原形状的特征信息。A method of mesh simplification using greedy algorithm for vertex cover problems is presented in this paper. With this method, automatic maximum simplification can be realized by selecting minimum vertex sets to cover edges. Salient features of the original shapes are preserved in the simplified mesh. Experiment results show promising results of considerably good quality with reduced time complexity and well-preserved salient features of original shapes.

关 键 词：网格简化 保特征 顶点覆盖 贪心算法 

分 类 号：TP319.9[自动化与计算机技术—计算机软件与理论]