New efficient approximate convex hull algorithm for very large planar point set

A new approximate convex hull algorithm for very large planar point set is presented.That is multi-direction extreme value approximate convex hull algorithm,and is called MDEV for short.Firstly,according to the control parameter given by the user,a series of extreme directions are created automatically,and every direction has its corresponding extreme value expression;Secondly,the planar point set is scanned,and the information of the extreme value points in every direction is updated according to the coordinates of every point in the point set;At last,the extreme value points are assembled in a certain order and the duplicate ones are gotten rid,then the approximate convex hull is gained.The experiment shows that the algorithm is very efficient.It can be used in the situation,which is rigor for executing time but not for precision.Also,it can be used as a preprocessing course of efficient convex hull algorithms.