摘要
在研究中轴性质的基础上,给出了一种全新的求解凸多边形直径算法。该算法首先求出凸多边形的中轴,再根据中轴的两个端点确定直径。算法简单,并在无预处理的情况下达到了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）.
出处
《计算机工程与应用》
CSCD
北大核心
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)。
关键词
凸多边形
直径
中轴
主轴
convex polygon
diameter
middle axis
main axis
