基于贪心算法思想的凸多边形最优三角剖分算法研究

摘要：

当将多边形分割成互不相交的三角形的弦长之和最小时，称为最优三角剖分。在动态规划算法实现此功能的时间复杂度O(n3)，空间复杂度O(n2)[1]，采用贪心算法的时间复杂度是O(n2)，空间复杂度是O(n)，算法效率有明显的提升。贪心算法思想的最优剖分算法推广到三维空间，实现对多面体最优三角形椎体的剖分能得到非常现实的应用。

关键词：最优三角剖分、最小三角弦、动态规划算法、贪心算法、最优三角形椎体

分类号：TP311(计算技术、计算机技术)

在线出版日期：2015-01-09（万方平台首次上网日期，不代表论文的发表时间）

页数：共2页

页码：8555-8556