Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/118887
Title: Fundamental Computational Geometry on the GPU
Authors: CAO THANH TUNG
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.
URI: http://scholarbank.nus.edu.sg/handle/10635/118887
Appears in Collections:Ph.D Theses (Open)

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

OPEN

NoneView/Download

Page view(s)

158
checked on Jan 13, 2018

Download(s)

314
checked on Jan 13, 2018

Google ScholarTM

Check


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