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

• 作者: 唐厚君 戴海鹏
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 凸多边形:直径 计算几何
• 年，卷（期）: 2011,（3）
• 所属期刊栏目: 研究、探讨
• 页码范围: 44-46
• 分类号: TP301.6
• 字数: 3234字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.2011.03.013

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	唐厚君	上海交通大学电子信息与电气工程学院	127	809	16.0	23.0
2	戴海鹏	上海交通大学电子信息与电气工程学院	1	2	1.0	1.0