求凸多边形直径的改进算法

摘要：

求凸多边形直径是计算几何中的一个基本问题,在Preparata-Shamos算法的基础上,提出了采用动态规划和二分查找的算法,不需要对凸多边形进行预处理,使整个算法的时间复杂度降低到O(n)级别.对算法实现的理论分析结果进行了验证,实验结果表明算法具有较高效率.

关键词：凸多边形:直径、计算几何

所属期刊栏目：47

分类号：TP301.6(计算技术、计算机技术)

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

页数：共3页

页码：44-46