Reducing the Number of Points on the Convex Hull Calculation Using the Polar Space Subdivision in E2
Václav Skala, Michal Smolik, Zuzana Majdisova · 2016
A convex hull of points in E2is used in many applications. In spite of low computational complexity O(h logn) it takes considerable time if large data processing is needed. We present a new algorithm to speed up any planar convex hull calculation. It is based on a polar space subdivision and speed up known convex hull algorithms of 3,7 times and more. The algorithm estimates the central point using 10% of the data, this point is taken as the origin for the polar subdivision. The space subdivision enables a fast and very efficient reduction of the given points, which cannot contribute to the final convex hull. The proposed algorithm iteratively approximates the convex hull, leaving only a small number of points for the final processing, which is performed using a "standard" algorithm. Non-eliminated points are then processed by a selected standard convex hull algorithm. The algorithm is simple and easy to implement. Experiments proved numerical robustness as well.