  This paper presents a fast implementation of the Graham scan on the GPU. The
proposed algorithm is composed of two stages: (1) two rounds of preprocessing
performed on the GPU and (2) the finalization of finding the convex hull on the
CPU. We first discard the interior points that locate inside a quadrilateral
formed by four extreme points, sort the remaining points according to the
angles, and then divide them into the left and the right regions. For each
region, we perform a second round of filtering using the proposed preprocessing
approach to discard the interior points in further. We finally obtain the
expected convex hull by calculating the convex hull of the remaining points on
the CPU. We directly employ the parallel sorting, reduction, and partitioning
provided by the library Thrust for better efficiency and simplicity.
Experimental results show that our implementation achieves 6x ~ 7x speedups
over the Qhull implementation for 20M points.
