一种改进的求凸多边形直径的最优算法  

An Improved Optimal Algorithm for Computing the Diameter of Convex Polygons

作　　者：曲吉林[1] 

机构地区：[1]山东财政学院计算机科学与工程系,济南250014

出　　处：《计算机工程与应用》2005年第26期94-96,共3页Computer Engineering and Applications

摘　　要：求凸多边形的直径是计算几何中的一个基本问题。该文对Preparata-Shamos提出的最优算法进行了改进,使距离比较中的运算的次数从44n次减少到14n次,并减少了平行边的处理时间。实验结果表明,算法的运行时间减少到原来的53%。Computing the diameter of convex polygons is a fundamental problem in computational geometry.This paper has improved the optimal algorithm presented by Preparata and Shamos for computing the diameters of convex polygons, The improved algorithm reduces the calculating times in distance comparison from 44n to 14n,and reduces the complexity of dealing with parallel edges.The experiment result shows the run time of the algorithm is reduced by 47 percent.

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

分 类 号：TP391[自动化与计算机技术—计算机应用技术]