求凸多边形直径的改进算法

doi:10.3778/j.issn.1002-8331.2011.03.013

计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (3): 44-46.DOI: 10.3778/j.issn.1002-8331.2011.03.013

求凸多边形直径的改进算法

戴海鹏，唐厚君

上海交通大学电子信息与电气工程学院，上海 200240

收稿日期:2009-05-15 修回日期:2009-08-18 出版日期:2011-01-21 发布日期:2011-01-21
通讯作者: 戴海鹏

Improved algorithm for computing diameter of convex polygons

DAI Haipeng，TANG Houjun

School of Electronic Information and Electrical Engineering，Shanghai Jiaotong University，Shanghai 200240，China

Received:2009-05-15 Revised:2009-08-18 Online:2011-01-21 Published:2011-01-21
Contact: DAI Haipeng

摘要/Abstract

摘要： 求凸多边形直径是计算几何中的一个基本问题，在Preparata-Shamos算法的基础上，提出了采用动态规划和二分查找的算法，不需要对凸多边形进行预处理，使整个算法的时间复杂度降低到O(n)级别。对算法实现的理论分析结果进行了验证，实验结果表明算法具有较高效率。

关键词: 凸多边形, 直径, 计算几何

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.

Key words: convex polygon, diameter, computational geometry

中图分类号:

TP301.6

戴海鹏，唐厚君. 求凸多边形直径的改进算法[J]. 计算机工程与应用, 2011, 47(3): 44-46.

DAI Haipeng，TANG Houjun. Improved algorithm for computing diameter of convex polygons[J]. Computer Engineering and Applications, 2011, 47(3): 44-46.

[1]	杨晓文，曹山海，韩燮. 基于边界特征的三维模型分割[J]. 计算机工程与应用, 2019, 55(4): 214-218.
[2]	钟玮1，2，刘日华3，陈宝兴1，2. 一类特殊三维六度环面网络的直径公式[J]. 计算机工程与应用, 2019, 55(13): 119-122.
[3]	周后卿1，徐幼专2. 基于网络拓扑图的树的代数连通度[J]. 计算机工程与应用, 2017, 53(3): 106-109.
[4]	许孝盛1，靳萍2，郑稳2. 室内座椅线框图识别[J]. 计算机工程与应用, 2016, 52(23): 196-202.
[5]	钟玮，陈宝兴. 计算循环群上4度Bi-Cayley网络直径的快速算法[J]. 计算机工程与应用, 2015, 51(14): 67-71.
[6]	傅天裕1，2，罗永龙1，2，郭良敏1，2，孙玲玲1，2. 保护私有信息的两多边形相交面积计算[J]. 计算机工程与应用, 2014, 50(9): 37-40.
[7]	吴芬1，仲红1，2，石润华1，2. 隐私保护的费马问题极值计算协议[J]. 计算机工程与应用, 2014, 50(4): 77-80.
[8]	魏葆雅1，刘日华2，陈宝兴1. 双环Petersen网络直径公式及最优路由算法[J]. 计算机工程与应用, 2013, 49(5): 81-83.
[9]	宋来忠1，彭刚2，沈艳军1. 参数曲面多边形区域上变形的伸缩因子与实验[J]. 计算机工程与应用, 2011, 47(12): 192-195.
[10]	王三¹，刘润涛²，王洪艳¹. 求两个相交凸多边形并的凸包及交的算法[J]. 计算机工程与应用, 2010, 46(5): 154-156.
[11]	刘辉，方木云，杭婷婷，侯海金. 最优无向双环网络G（N；±1，±s）的构造[J]. 计算机工程与应用, 2010, 46(33): 88-90.
[12]	符祖峰¹，罗文俊²，童玲¹. 一个保护私有信息的线段与椭圆相交判定协议[J]. 计算机工程与应用, 2010, 46(17): 77-80.
[13]	张彩云，罗永龙，石磊. 关于安全判定点和区间包含关系的解决方法[J]. 计算机工程与应用, 2010, 46(17): 107-109.
[14]	王洪艳¹，刘润涛²，王三¹. 简单多边形核求解新算法[J]. 计算机工程与应用, 2010, 46(17): 166-168.
[15]	王珽，罗文俊. 基于阈值的点线距离与位置关系保密判定协议[J]. 计算机工程与应用, 2010, 46(13): 87-89.

求凸多边形直径的改进算法

Improved algorithm for computing diameter of convex polygons

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics