  This paper presents a practical GPU-accelerated convex hull algorithm and a
novel Sorting-based Preprocessing Approach (SPA) for planar point sets. The
proposed algorithm consists of two stages: (1) two rounds of preprocessing
performed on the GPU and (2) the finalization of calculating the expected
convex hull on the CPU. We first discard the interior points that locate inside
a quadrilateral formed by four extreme points, and then distribute the
remaining points into several (typically four) sub regions. For each subset of
points, we first sort them in parallel, then perform the second round of
discarding using SPA, and finally form a simple chain for the current remaining
points. A simple polygon can be easily generated by directly connecting all the
chains in sub regions. We at last obtain the expected convex hull of the input
points by calculating the convex hull of the simple polygon. We use the library
Thrust to realize the parallel sorting, reduction, and partitioning for better
efficiency and simplicity. Experimental results show that our algorithm
achieves 5x ~ 6x speedups over the Qhull implementation for 20M points. Thus,
this algorithm is competitive in practical applications for its simplicity and
satisfied efficiency.
