摘要
求凸多边形的直径是计算几何中的一个基本问题。该文对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.
出处
《计算机工程与应用》
CSCD
北大核心
2005年第26期94-96,共3页
Computer Engineering and Applications
关键词
计算几何
凸多边形
直径
算法
computational geometry,convex polygon,diameter,algorithm
