Please use this identifier to cite or link to this item: https://doi.org/10.1145/2159616.2159623
Title: Computing 2D constrained Delaunay triangulation using the GPU
Authors: Qi, M.
Cao, T.-T.
Tan, T.-S. 
Keywords: computational geometry
GPGPU
Voronoi diagram
Issue Date: 2012
Source: Qi, M.,Cao, T.-T.,Tan, T.-S. (2012). Computing 2D constrained Delaunay triangulation using the GPU. Proceedings - I3D 2012: ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games : 39-46. ScholarBank@NUS Repository. https://doi.org/10.1145/2159616.2159623
Abstract: We propose the first GPU solution to compute the 2D constrained Delaunay triangulation (CDT) of a planar straight line graph (PSLG) consisting of points and edges. There are many CPU algorithms developed to solve the CDT problem in computational geometry, yet there has been no known prior approach using the parallel computing power of the GPU to solve this problem efficiently. For the special case of the CDT problem with a PSLG consisting of just points, which is the normal Delaunay triangulation problem, a hybrid approach has already been presented that uses the GPU together with the CPU to partially speed up the computation. Our work, on the other hand, accelerates the whole computation by the GPU. Our implementation using the CUDA programming model on NVIDIA GPUs is numerically robust with good speedup, of up to an order of magnitude, compared to the best sequential implementations on the CPU. This result is reflected in our experiment with both randomly generated PSLGs and real world GIS data with millions of points and edges. © 2012 ACM.
Source Title: Proceedings - I3D 2012: ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games
URI: http://scholarbank.nus.edu.sg/handle/10635/40283
ISBN: 9781450311946
DOI: 10.1145/2159616.2159623
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

17
checked on Dec 11, 2017

Page view(s)

55
checked on Dec 9, 2017

Google ScholarTM

Check

Altmetric


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