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

Improved algorithm for computing diameter of convex polygons

求凸多边形直径是计算几何中的一个基本问题,在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.