@Article{Gao:2013:GGA,
  author =       "Mingcen Gao and Thanh-Tung Cao and Ashwin Nanjappa
                  and Tiow-Seng Tan and Zhiyong Huang",
  title =        "{gHull}: a {GPU} Algorithm for {3D} Convex Hull",
  journal =      "{ACM} Transactions on Mathematical Software",
  volume =       "40",
  number =       "1",
  year =         "2013",
  month =        oct,
  pages =        "3:1--3:19",
  url =          "http://doi.acm.org/10.1145/2513109.2513112",
  accepted =     "4 April 2013",
  abstract =     "
                  A novel algorithm is presented to compute the convex
                  hull of a point set in $\mathbb{R}^3$ using the graphics
                  processing unit (GPU).  By exploiting the relationship
                  between the Voronoi diagram and the convex hull, the
                  algorithm derives the approximation of the convex hull from
                  the former.  The other extreme vertices of the convex hull
                  are then found by using a two-round checking in the digital
                  and the continuous space successively.  The algorithm does
                  not need explicit locking or any other concurrency control
                  mechanism, thus it can maximize the parallelism available
                  on the modern GPU.

                  The implementation using the CUDA programming model on
                  NVIDIA GPUs is exact and efficient.  The experiments show
                  that it is up to an order of magnitude faster than other
                  sequential convex hull implementations running on the CPU
                  for inputs of millions of points.  The works demonstrate
                  that the GPU can be used to solve non-trivial computational
                  geometry problems with significant performance benefit.",
}