%0 Journal Article
%A LIU Run-tao
%A WANG San
%A AN Xiao-hua
%T New method for computing convex hulls of point sets on plane
%D 2009
%R 10.3778/j.issn.1002-8331.2009.03.016
%J Computer Engineering and Applications
%P 58-59
%V 45
%N 3
%X A new algorithm of computing convex hulls of plane point sets is presented，based on the research on a large amount of algorithms of computing the convex hulls of plane point sets.In the algorithm，the four extreme points are first computed，which compose a quadrangle，then for the points out of the quadrangle we figure out which line sections they belong to in order with the method of bisection.For the points in the same line section，we just find out the points on the right side，then connect them with the two endpoints of the line section separately to compose a new polygon chain，then process each point in the same way until the last one.In this way，four monotonic chains of simple polygons are obtained，then the vertices of the convex hulls of the four monotonic chains are computed.Its time complexity is O（*n*）.All the vertices are the ones of the convex hull of the plane point set.The total time complexity of this algorithm is not more than O（*n* log *n*）.
%U http://cea.ceaj.org/EN/10.3778/j.issn.1002-8331.2009.03.016