Improved algorithm for computing diameter of convex polygons

doi:10.3778/j.issn.1002-8331.2011.03.013

Computer Engineering and Applications ›› 2011, Vol. 47 ›› Issue (3): 44-46.DOI: 10.3778/j.issn.1002-8331.2011.03.013

• 研究、探讨 • Previous Articles Next Articles

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

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

戴海鹏，唐厚君

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

通讯作者: 戴海鹏

Abstract

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

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

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

CLC Number:

TP301.6

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

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

[1]	YANG Xiaowen, CAO Shanhai, HAN Xie. Three-Dimensional Model Segmentation Based on Boundary Features [J]. Computer Engineering and Applications, 2019, 55(4): 214-218.
[2]	ZHONG Wei1，2, LIU Rihua3, CHEN Baoxing1，2. Diameter Formula for a Special 3D Hexagonal Torus [J]. Computer Engineering and Applications, 2019, 55(13): 119-122.
[3]	ZHOU Houqing1，XU Youzhuan2. Algebraic connectivity of trees based on network topology [J]. Computer Engineering and Applications, 2017, 53(3): 106-109.
[4]	XU Xiaosheng1, JIN Ping2, ZHENG Wen2. Recognition of indoor chair wireframe [J]. Computer Engineering and Applications, 2016, 52(23): 196-202.
[5]	ZHONG Wei, CHEN Baoxing. Fast algorithm of calculating diameter for Bi-Cayley graph with 4 degrees on cyclic group [J]. Computer Engineering and Applications, 2015, 51(14): 67-71.
[6]	FU Tianyu1，2, LUO Yonglong1，2, GUO Liangmin1，2, SUN Lingling1，2. Privacy preserving calculating intersection area of two polygons [J]. Computer Engineering and Applications, 2014, 50(9): 37-40.
[7]	WU Fen1, ZHONG Hong1，2, SHI Runhua1，2. Privacy-preserving computation protocol for fermat problem’s extreme values [J]. Computer Engineering and Applications, 2014, 50(4): 77-80.
[8]	WEI Baoya1, LIU Rihua2, CHEN Baoxing1. Diameter formula and optimal routing algorithm for double-loops Petersen networks [J]. Computer Engineering and Applications, 2013, 49(5): 81-83.
[9]	LV Jianhua, ZHOU Huachun, QIU Luwei, ZHANG Hongke. Implementation of authentication and authorization of proxy mobile IPv6 [J]. Computer Engineering and Applications, 2012, 48(22): 109-116.
[10]	YU Gang, LIU Gang. Spatial fussy query on shape cognition of 2D objects [J]. Computer Engineering and Applications, 2012, 48(16): 185-189.
[11]	WANG San¹，LIU Run-tao²，WANG Hong-yan¹. Algorithms for convex hull of union and intersection of two intersecting convex polygons [J]. Computer Engineering and Applications, 2010, 46(5): 154-156.
[12]	LIU Hui，FANG Mu-yun，HANG Ting-ting，HOU Hai-jin. Research on construction of best bidirectional double-loop networks G（N；±1，±s） [J]. Computer Engineering and Applications, 2010, 46(33): 88-90.
[13]	FU Zu-feng¹，LUO Wen-jun²，TONG Ling¹. Protocol for privacy-preserving intersect-determination of line segment and elliptical [J]. Computer Engineering and Applications, 2010, 46(17): 77-80.
[14]	ZHANG Cai-yun，LUO Yong-long，SHI Lei. Security solution to points-range inclusion problem [J]. Computer Engineering and Applications, 2010, 46(17): 107-109.
[15]	WANG Hong-yan¹，LIU Run-tao²，WANG San¹. New algorithm to calculate kernel of simple polygon [J]. Computer Engineering and Applications, 2010, 46(17): 166-168.

Improved algorithm for computing diameter of convex polygons

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics