摘要
计算一般多边形凸包的算法时间复杂度为O(n^2)。本文提出一种求简单多边形凸包的算法,并证明了它在最坏情况下的时间复杂度为O(n)。
Generally, the time - complexity of the algorithm is O( n2 )for calculating the convex hulls of polygons. This paper gives the algorithm for calculating the convex hulls of simple polygons, and proves that its time - complexity is O ( n) in the worst case.
出处
《计算机应用与软件》
CSCD
1998年第5期38-41,共4页
Computer Applications and Software
基金
山东省自然科学基金(Y97G08108)
关键词
计算机图形学
多边形
凸包
最优算法
Computer graphics, polygon, convex hull, optimal algorithm.
