Please use this identifier to cite or link to this item:
Title: Fundamental Computational Geometry on the GPU
Keywords: GPGPU, Delaunay triangulation, Voronoi diagram, convex hull, incremental insertion, bilateral flipping
Issue Date: 16-Jun-2014
Source: CAO THANH TUNG (2014-06-16). Fundamental Computational Geometry on the GPU. ScholarBank@NUS Repository.
Abstract: This thesis presents two approaches for solving several fundamental computational geometry problems on the GPU. In the first approach, we obtain a sketch in digital space, followed by deriving an approximation in continuous space, and finally transforming it into the exact solution. The sketch we use is the digital Voronoi diagram computed using our Parallel Banding Algorithm. In the second approach, we combine incremental insertion with local transformations, and in contrast it works completely in continuous space. This works straightforwardly for the 2D Delaunay triangulation problem, while 3D convex hull needs a novel flipping schedule and 3D Delaunay triangulation requires a hybrid GPU-CPU approach. Overall, both approaches focus on providing a high level of fine-grained parallelism, 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.
Appears in Collections:Ph.D Theses (Open)

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
CaoTT.pdf6.62 MBAdobe PDF



Page view(s)

checked on Jan 13, 2018


checked on Jan 13, 2018

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.