一种求凸多边形直径的改进算法.pdfVIP

一种求凸多边形直径的改进算法 戴海鹏，钟溢原，唐厚君，刘伟 (上海交通大学 电子信息与电气工程学院， 上海 200240) 摘 要: 求凸多边形直径是计算几何中的一个基本问题，本文在Preparata-Shamos 算法的基础上，提出了采 用分治和二分查找的算法，不需要对凸多边形进行预处理，使整个算法的时间复杂度降低到O(n) 级别。最 后给出了此算法的实现，对理论分析结果进行了验证。实验结果表明此算法效率很高。 关键词: 凸多边形；直径；计算几何；算法 An Improved Algorithm for Computing the Diameter of Convex Polygons DAI Hai-peng, ZHONG Yi-yuan, TANG Hou-jun, LIU Wei (School of Electronic, Information and Electrical Engineering, Shanghai Jiao Tong University, Shanghai, China, 200240) 【Abstract 】 Computing the diameter of convex polygons is a fundamental problem in computational geometry. This paper presents an algorithm adopting divide-and-conquer 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 result shows that the algorithm has a high efficiency. 【Key words 】convex polygon; diameter; computational geometry; algorithm 1 引言 找与该边距离最大的点，查找范围限于已处理的相 平面点集直径问题是计算几何中的基本问题 邻边的距离最大点之间。查找范围的缩小使整个算 [1] ，在计算机图形学、模式识别、图像处理、数据 法的时间复杂度降低到O(n) ，实现了算法的优化且 挖掘以及CAD /CAM等领域中都有具体应用。其解 不需要预处理过程。 决方法是先求出点集的凸包，再求凸包的最远点 对，从而将问题进一步转化为求该凸包的直径，则 2 算法介绍 直径所对应的点对即为原问题的解。因此，平面点 2.1 夹角序列算法 集的直径问题可以转化为求凸多边形直径的问题。 首先引入文献[3]中的一个引理。 给定凸多边形P 顶点序列 p n (p p ) ，其 设四个三角形ABC 、A CE 、AEF 与AFG 的位 { } i i 1 n=+k k 直径是多边形n 个顶点间的最大距离。国内外许多 置如图 1 所示，