An Acceleration And Improved Algorithm Of Convex Hull Computing

This article researches mostly on how to improve the Convex Hull Algorithm of Planar Point Set. The classical method contacts this problem with the sorting algorithm. For example, Graham's method. It aims at any instance especially the worst instance. The runtime complexity is O(nlogn) in these method. The complexity of runtime is the least in the worst instance. Other algorithm, for example Jarvis method, get better result in some instance, But runtime complexity is O (n2) in the worst instance. Research show that mostly problem is out the worst instance. So, in these instances, we should find out a new method to improve the efficiency for this problem. This article put forward a new method for a problem in general (not in the worst) instance. Adopting an acceleration method in the basis of classical .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. Because only the boundary of a point set is the critical to a convex hull, other point needs not considered. But in classical algorithm, all the point takes part in the calculation. The acceleration algorithm can calculate a boundary, close in a big part of point, but closed in by the convex hull. Afterward, using less time remove the point closed in from point set. According to the research and test, only very little point is keep down. In the same time, to the point set obeying even distributing and Zt distributing, which lie in the most problem, using an acceleration factor optimize the method ,it can work even better . At last, make use of the ordered-partly point set after the first step to improve the classical algorithm and to optimize the process. Can make the even runtime reach O (n). But in the worst instance, it is still 0 (nlogn).