  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.
