Incremental Delaunay Triangulation on GPUs

Abstract—Delaunay Triangulation of points on a plane is an essential and indispensible technique in numerous fields of computing from computational geometry and finite elements method to wireless networks. In this project I implemented a parallelized extrapolation based incremental algorithm for the exact delaunay triangulation of large point sets (in 2D) on GPUs using CUDA. What makes this algorithm unique is the fact that it can be applied to an online setting in which the point are discovered radially. The algorithm achieves a reasonable degree of parallelism, by expanding the triangulations from certain seed values in the domain on the GPU and by allowing rare incomplete triangulations to be completed on CPU. Subtle tricks like data replication and bucketing were used although the algorithm has a lot of scope for future improvements. I