New efficient algorithm for creating convex hull for planar point set

This paper presented a new algorithm for creating convex hull for planar point set.It used the strategy of divide-conquer to calculate the convex hull by triangle-region processing,finding trait-points in pair by means of trait-angle calculation,decreasing the scale of the problem by the mechanism of initial triangle-region partition and updating,thereby rapidly approaching to the edge of the convex hull.For large scale data set of points,the idea of iteration was introduced in,which used the ability of quickly deleting the non convex hull points to accelerate the process of getting convex hull,making the performance of the algorithm enhanced further.Both of the time complexity and the space complexity of the algorithm are O(n).The experiments manifest that it is a feasible,efficient and stable algorithm.Furthermore,this algorithm is easy to be extended to three-dimensional space as well as be improved to parallel type.