| 基于夹角符号序列的凸多边形直径优化算法 |
| |
| 引用本文： | 李博,刘润涛,余存光.基于夹角符号序列的凸多边形直径优化算法[J].哈尔滨理工大学学报,2008,13(2):43-45. |
| |
| 作者姓名： | 李博 刘润涛 余存光 |
| |
| 作者单位： | 哈尔滨理工大学,应用科学学院,黑龙江,哈尔滨,150080 |
| |
| 基金项目： | 国家自然科学基金
,
黑龙江省教育厅科学技术研究项目 |
| |
| 摘 要： | 求凸多边形直径是计算几何中的一个基本问题,本文在夹角符号序列算法的基础上,提出并实现了采用对分查找的算法,使整个算法的时间复杂度降低到O(nlogn).该算法简单,运行效率高.
|
| 关 键 词： | 凸多边形 凸壳直径 对分查找 计算几何 |
| 文章编号： | 1007-2683(2008)02-0043-02 |
| 修稿时间： | 2006年12月22 |
An Optimal Angle Sign Sequence Algorithm for Calculating the Diameter of Convex Polygons |
| |
| LI Bo,LIU Run-tao,YU Cun-guang.An Optimal Angle Sign Sequence Algorithm for Calculating the Diameter of Convex Polygons[J].Journal of Harbin University of Science and Technology,2008,13(2):43-45. |
| |
| Authors: | LI Bo LIU Run-tao YU Cun-guang |
| |
| Abstract: | 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. |
| |
| Keywords: | convex polygon diameter of convex hull binary search computational geometry |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
