2023/03/19 by Roberto E. Polanco Carrasco, Héctor Ferrada, Carrasco, Roberto +5
Computer Science · Engineering · #Advanced Image and Video Retrieval Techniques #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Distributed #FOS: Computer and information sciences #Parallel #Robotics and Sensor-Based Localization #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2303.10581
openalex publication_date 2023/03/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The Convex Hull algorithm is one of the most important algorithms in computational geometry, with many applications such as in computer graphics, robotics, and data mining. Despite the advances in the new algorithms in this area, it is often needed to improve the performance to solve more significant problems quickly or in real-time processing. This work presents an experimental evaluation of GPU filters to reduce the cost of computing the 2D convex hull. The technique first performs a preprocessing of the input set, filtering all points within an eight-vertex polygon in logarithmic time, to obtain a reduced set of candidate points. We use parallel computation and the use of the Manhattan distance as a metric to find the vertices of the polygon and perform the point filtering. For the filtering stage we study different approaches; from custom CUDA kernels to libraries such as Thrust and CUB. Three types of point distributions are tested: a normal distribution (favorable case), circumference (the worst case), and a case where points are shifted randomly from the circumference (intermediate case). Experimental evaluation shows that the GPU filtering algorithm can be up to 23x faster than a sequential CPU implementation, and the whole convex hull computation can be up to 30x faster than the fastest implementation provided by the CGAL library.