Today I read a paper titled “Finding Convex Hulls Using Quickhull on the GPU”
The abstract is:
We present a convex hull algorithm that is accelerated on commodity graphics hardware
We analyze and identify the hurdles of writing a recursive divide and conquer algorithm on the GPU and divise a framework for representing this class of problems
Our framework transforms the recursive splitting step into a permutation step that is well-suited for graphics hardware
Our convex hull algorithm of choice is Quickhull
Our parallel Quickhull implementation (for both 2D and 3D cases) achieves an order of magnitude speedup over standard computational geometry libraries