A Paradigm for Divide and Conquer Algorithms on the GPU and its Application to the Quickhull Algorithm

We present a divide and conquer paradigm for dataparallel architectures and use it to implement the Quickhull algorithm to find convex hulls. Divide and conquer is a powerful concept in programming which divides data into smaller subproblems (the divide stage), which can then be recursively solved (the conquer stage) quickly. However in the absence of recursion support on current GPUs, it is unclear how to map such algorithms onto the GPU efficiently.