A Divide-and-Conquer Algorithm of Delaunay Triangulation with GPGPU

In this study, we will parallelize the D&C algorithm with CUDA. In stead of recursive programming in D&C, the recursive stack is implemented on the host side (CPU) and the merge operation is executes on GPU in parallel. Since the recursive stack is a fully binary tree in this algorithm, the merge operations on the nodes in each layer of the binary tree can be performed synchronously. In this data-parallel computation, with the careful management of data structure, the data of each node can be arranged in the same block and no need to share data between threads, so the parallelism is not broken.