Please use this identifier to cite or link to this item:
Title: Delaunay triangulation in R3 on the GPU
Keywords: Delaunay triangulation, GPU, computational geometry, parallel computing, algorithms, star splaying
Issue Date: 28-Nov-2012
Citation: ASHWIN NANJAPPA (2012-11-28). Delaunay triangulation in R3 on the GPU. ScholarBank@NUS Repository.
Abstract: This thesis presents massively parallel algorithms to compute the 3D Delaunay triangulation efficiently and robustly on the GPU. Our CUDA implementations of these algorithms obtain a speedup of up to 6 times over comparable methods. gDel3D is a heterogeneous GPU-CPU algorithm that performs massively parallel insertion and flipping on the GPU to compute a nearly-Delaunay triangulation. It fixes this result on the CPU using a conservative star splaying approach to obtain 3D Delaunay. gStar4D is a GPU algorithm that uses the neighbourhood information in the digital Voronoi diagram to create stars of each input point on the GPU. It uses an unique star splaying approach to splay these 4D stars in parallel, make them consistent and extract the 3D Delaunay result. This thesis also shows that these techniques can be adapted to solve other computational geometry problems in R3 and R4 using the GPU.
Appears in Collections:Ph.D Theses (Open)

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
AshwinNanjappa.pdf5.23 MBAdobe PDF



Page view(s)

checked on Nov 24, 2018


checked on Nov 24, 2018

Google ScholarTM


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