Faster Convex Hull Computation by Reducing Computational Overhead and Time
Ngangbam Herojit Singh, Laipharkpam Dolendro Singh · International journal of advanced computer science · 2015
Finding the convex hull of a point set has applications in research fields as well as industrial tools. This paper presents a pre-processing algorithm for computing convex hull vertices in a 2D spatial point set.Based on the position of extreme points we divide the exterior points into four groups bounded by rectangles(p-Rect). Then inside each p-Rect we recursively find and check the extreme points to verify if there are eligible to be convex hull points or not.The process gives a small set of candidates points for convex hull computation.Efficiency of the algorithm is evaluated with respect to time and space. Performance comparison with other classical algorithms shows that implementation of this pre-processing algorithm significantly improves their performance by reducing computational overhead and time.