A Pre-processing Algorithm for Faster Convex Hull Computation

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 they are eligible to be convex hull points or not. The process gives a small set of candidate 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.