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

摘要

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.%针对三角网格简化,设计了求解顶点覆盖问题的贪心算法,通过贪心选择最小的顶点集去＂覆盖＂边集,同时保留被简化网格的特征信息,自动实现最大程度简化。给出的实例也表明简化后的网格质量良好,算法既降低了时间复杂度又保持了原形状的特征信息。