gScan: Accelerating Graham Scan on the GPU

Gang Mei
Institute of Earth and Environmental Science, University of Freiburg, Albertstr.23B, D-79104, Freiburg im Breisgau, Germany
arXiv:1508.05931 [cs.CG], (22 Aug 2015)


   title={gScan: Accelerating Graham Scan on the GPU},

   author={Mei, Gang},






Download Download (PDF)   View View   Source Source   



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.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: