Rapid preconditioning of data for accelerating convex hull computations
Oswaldo Cadenas, Graham M. Megson · Electronics Letters · 2014
Given a dataset of two‐dimensional points in the plane with integer coordinates, the method proposed reduces a set of n points down to a set of s points s ≤ n , such that the convex hull on the set of s points is the same as the convex hull of the original set of n points. The method is O ( n ). It helps any convex hull algorithm run faster. The empirical analysis of a practical case shows a percentage reduction in points of over 98%, that is reflected as a faster computation with a speedup factor of at least 4.