中轴求凸多边形直径算法  

Algorithm for computing diameter of convex polygon by middle axis

作　　者：董秀山[1] 刘润涛[2] 

机构地区：[1]哈尔滨理工大学应用科学学院,哈尔滨150080 [2]哈尔滨理工大学信息与科学计算技术研究所,哈尔滨150080

出　　处：《计算机工程与应用》2008年第32期51-52,89,共3页Computer Engineering and Applications

基　　金：国家自然科学基金(the National Natural Science Foundation of China under Grant No.10571037);黑龙江省教育厅资助项目(the Heilongjiang Province's Education-funded Projects of China under Grant No.11511027)。

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

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

分 类 号：TP391[自动化与计算机技术—计算机应用技术]