摘要
求凸多边形直径是计算几何中的一个基本问题,本文在夹角符号序列算法的基础上,提出并实现了采用对分查找的算法,使整个算法的时间复杂度降低到O(nlogn).该算法简单,运行效率高.
Calculating the diameter of convex polygon is a fundamental problem in computational geometry. This paper proposed and implemented a binary search algorithm based on angle sign sequence algorithm. Its time complexity is O（nlogn）. The algorithm is simple, effective and applicable.
出处
《哈尔滨理工大学学报》
CAS
2008年第2期43-44,48,共3页
Journal of Harbin University of Science and Technology
基金
国家自然基金资助项目(10571037)
黑龙江省教育厅资助项目(11511087)
关键词
凸多边形
凸壳直径
对分查找
计算几何
convex polygon
diameter of convex hull
binary search
computational geometry
