| 求凸多边形直径的改进算法 |
| |
| 引用本文： | 戴海鹏,唐厚君.求凸多边形直径的改进算法[J].计算机工程与应用,2011,47(3):44-46. |
| |
| 作者姓名： | 戴海鹏 唐厚君 |
| |
| 作者单位： | 上海交通大学 电子信息与电气工程学院，上海 200240 |
| |
| 摘 要： | 求凸多边形直径是计算几何中的一个基本问题，在Preparata-Shamos算法的基础上，提出了采用动态规划和二分查找的算法，不需要对凸多边形进行预处理，使整个算法的时间复杂度降低到O(n)级别。对算法实现的理论分析结果进行了验证，实验结果表明算法具有较高效率。
|
| 关 键 词： | 凸多边形 直径 计算几何 |
| 收稿时间： | 2009-5-15 |
| 修稿时间： | 2009-8-18
|
Improved algorithm for computing diameter of convex polygons |
| |
| DAI Haipeng,TANG Houjun.Improved algorithm for computing diameter of convex polygons[J].Computer Engineering and Applications,2011,47(3):44-46. |
| |
| Authors: | DAI Haipeng TANG Houjun |
| |
| Affiliation: | School of Electronic Information and Electrical Engineering，Shanghai Jiaotong University，Shanghai 200240，China |
| |
| Abstract: | Computing the diameter of convex polygons is a fundamental problem in computational geometry.This paper presents an algorithm adopting dynamic planning 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 results show that the algorithm has a high efficiency. |
| |
| Keywords: | convex polygon diameter computational geometry |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程与应用》浏览原始摘要信息 |
|
点击此处可从《计算机工程与应用》下载全文 |
