A Gird-aided Algorithm for Determining the Minimum Convex Hull of Planar Points Set

This paper presents a gird aided method for determining the convex hull of large amount data,the total time complexity of algorithm can achieve about O(n).The basic idea of the method is as follows.First,build a gird field which can cover with all planar points;then,figure out the position of every point in the gird field(such as the row and column place in the field).Afterwards,reserve the points which are in the gird field of leftmost(or rightmost) column or top(or bottom) row.Finally,execute Graham's algorithm to generate the convex hull with reserved points.The result of the tests indicates that there has some relationship between grid parameters and algorithm efficiency.Such as,with the increase in row-column number,the computational efficiency first rapid increase,followed by a gradual decrease.Additionally,when the row-column number select the evolution of total planar points' number,the pretreatment effect of the algorithm almost reach maximum.Furthermore,with the increase of the number of planar points,the elimination efficiency of gird aided method improves.