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

Improved algorithm for computing diameter of convex polygons

作　　者：戴海鹏[1] 唐厚君[1] 

机构地区：[1]上海交通大学电子信息与电气工程学院,上海200240

出　　处：《计算机工程与应用》2011年第3期44-46,共3页Computer Engineering and Applications

摘　　要：求凸多边形直径是计算几何中的一个基本问题,在Preparata-Shamos算法的基础上,提出了采用动态规划和二分查找的算法,不需要对凸多边形进行预处理,使整个算法的时间复杂度降低到O(n)级别。对算法实现的理论分析结果进行了验证,实验结果表明算法具有较高效率。Computing the diameter of convex polygons is a fundamental problem in computational geometry.This paper presents an algorithm adopting dynamic planning and binary searching approach based on the algorithm developed by Preparate and Shamos.This algorithm needn’t pretreatment for convex polygon and reduces the time complexity to O（n） level.Finally,an implement of the algorithm is given to verify the result of the theoretical analysis.The experimental results show that the algorithm has a high efficiency.

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]