Effective Construction of Convex Hull Algorithms
Peter Mitura, Ivan Šimeček, Ivan Kotenkov · 2017
Finding the convex hull of a set of points in a plane is one of the most common problems in computational geometry. We survey known algorithms for solving this problem and look into methods of their effective and parallel implementation. A simple generator of random input datasets is created, with an option to control the number of points on the resulting hull. We implement all surveyed algorithms along with their optimizations and compare them using our generator. Our measurements show, that Quickhull algorithm using optimizations proposed by Hoang and Linh [1] has the best performance among the implemented methods and is faster than the current state of the art libraries.