Algorithm for computing diameter of convex polygon by middle axis

doi:10.3778/j.issn.1002-8331.2008.32.015

Computer Engineering and Applications ›› 2008, Vol. 44 ›› Issue (32): 51-52.DOI: 10.3778/j.issn.1002-8331.2008.32.015

• 理论研究 • Previous Articles Next Articles

Algorithm for computing diameter of convex polygon by middle axis

DONG Xiu-shan¹,LIU Run-tao²

1．College of Applied Science，Harbin University of Science and Technology，Harbin 150080，China
2.Institution of Information and Scientific Computing Technology，Harbin University of Science and Technology，Harbin 150080，China

Received:2007-12-10 Revised:2008-02-27 Online:2008-11-11 Published:2008-11-11
Contact: DONG Xiu-shan

中轴求凸多边形直径算法

董秀山¹,刘润涛²

1.哈尔滨理工大学应用科学学院，哈尔滨 150080
2.哈尔滨理工大学信息与科学计算技术研究所，哈尔滨 150080

通讯作者: 董秀山

Abstract

Abstract: A brand new algorithm for computing the diameter of a convex polygon is proposed，based on the research on the properties of the middle medial axis for a convex polygon.First the middle axis of a convex polygon is determined，then the diameter of the polygon can be computed by the two end points of the middle axis.The algorithm has no pre-processing，and its time complexity is O（n）.

Key words: convex polygon, diameter, middle axis, main axis

摘要： 在研究中轴性质的基础上，给出了一种全新的求解凸多边形直径算法。该算法首先求出凸多边形的中轴，再根据中轴的两个端点确定直径。算法简单，并在无预处理的情况下达到了O（n）。

关键词: 凸多边形, 直径, 中轴, 主轴

DONG Xiu-shan¹,LIU Run-tao². Algorithm for computing diameter of convex polygon by middle axis[J]. Computer Engineering and Applications, 2008, 44(32): 51-52.

董秀山¹,刘润涛². 中轴求凸多边形直径算法[J]. 计算机工程与应用, 2008, 44(32): 51-52.

[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]	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.
[5]	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.
[6]	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.
[7]	YU Gang, LIU Gang. Spatial fussy query on shape cognition of 2D objects [J]. Computer Engineering and Applications, 2012, 48(16): 185-189.
[8]	DAI Haipeng，TANG Houjun. Improved algorithm for computing diameter of convex polygons [J]. Computer Engineering and Applications, 2011, 47(3): 44-46.
[9]	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.
[10]	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.
[11]	ZHANG Guo-xiang，YANG Ai-min. Minimum strong diameter orientations of 2-vertex multiplications [J]. Computer Engineering and Applications, 2009, 45(27): 56-58.
[12]	ZHANG Quan-bing，XU Yan，ZHANG Ai-ming，CHENG Hong. Depth from defocus based on uneven defocusing model [J]. Computer Engineering and Applications, 2009, 45(26): 166-168.
[13]	XI Ming-xian¹,MA Jian-guo¹,LIN Yi-min²,LI You-ping³. Measurement and analysis of Internet physical properties in Chinese Mainland [J]. Computer Engineering and Applications, 2009, 45(2): 95-98.
[14]	ZHOU Jian-qin^1,2,WANG Wen-juan². Conformation of optimal double-loop networks [J]. Computer Engineering and Applications, 2008, 44(35): 62-65.
[15]	KUANG Zhen-guo^1,2,NI Hong²,JI Zhi-hui^1,2. Research and performance optimization of streaming media online charging system [J]. Computer Engineering and Applications, 2008, 44(29): 115-118.

Algorithm for computing diameter of convex polygon by middle axis

中轴求凸多边形直径算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics