Fundamental Computational Geometry on the GPU

Abstract:

Geometric structures such as Voronoi diagram, Delaunay triangulation, convex hull and their variants are fundamental to computational geometry. Various algorithmic paradigms to construct them have been designed for both single-core and multi-core systems. Nonetheless, the enormous parallel computation power of the GPU has not been exploited well to solve these problems, since existing algorithms do not map straightforwardly to the GPU architecture that relies on regularized work and localized data to achieve good performance.

In this thesis, we present two approaches for solving some fundamental computational geometry problems on the GPU. In the first approach, we obtain a sketch of the desirable geometric structure in the digital space, followed by deriving an approximation in the continuous space, and finally transforming it into the exact solution. The sketch we use is the digital Voronoi diagram, which we compute using our Parallel Banding Algorithm on the GPU. This algorithm has optimal linear total work, high level of paralelism and excellent memory access pattern. Following this approach, we develop GPU algorithms to construct the 2D and 3D Delaunay triangulation and the 3D convex hull efficiently.

Our second approach combines the incremental insertion technique with local transformations, and in contrast to the first approach, it works completely in the continuous space. Points in the input are inserted in batches, and flipping are applied in different schedules to get to the final solution. We show that applying this approach to the 2D Delaunay triangulation problem, with the help of several heuristics, yields an even more efficient solution than with the first approach. On the other hand, the 3D convex hull problem needs a novel flipping schedule, while the 3D Delaunay triangulation requires a hybrid approach, with the help of the CPU, to obtain provably correct result.
The two algorithmic approaches in this thesis focus on providing a high level of fine-grained parallelism during execution, lacking of which is the main weakness of existing CPU algorithms when adapted to the GPU. This thesis thus provides a strong foundation for further work on solving computational geometry problems on the GPU.