An Acceleration Algorithm of Convex Hull Computing Bace on the normal school
Hao Xiao-ju · Journal of Langfang Teachers College · 2009
This article researches mostly on how to improve the Convex Hull Algorithm of Planar Point Set.It worked very well in general instance and in the worst instance the runtime complexity is still O(nlogn).The primary idea of the acceleration algorithm focus on the boundary of point set.The acceleration algorithm can calculate a boundary,close in most of point,but closed in by the convex hull.In the same time,to the point set obeying even distributing and normal school,which lie in the most problem,using an acceleration factor optimize the method,it can work even better.It can make the even runtime reach O(n).But in the worst instance,it is still reach(nlogn).