An Efficient Convex Hull Algorithm for a Planer Set of Points

This paper contains a new efficient algorithm to construct the convex hull of a set of points in the plane. The proposed algorithm is able to find the points on the convex hull in boundary traversal order. When the convex hull has collinear points, the algorithm can detect all the collinear points on the hull without skipping the intermediate points. Furthermore it can deal with the data sets where coincident points appear. Two main methods have been used to make the algorithm efficient. First one is achieving parallelism which is done by partitioning the data set. Second one is data reduction which is done by removing unnecessary points at each step of processing. Further we have proved by experimental comparison, that the performance of the presented algorithm is better than interior point algorithm.