Please use this identifier to cite or link to this item: https://doi.org/10.1145/1342250.1342264
Title: Computing two-dimensional Delaunay triangulation using graphics hardware
Authors: Rong, G.
Tan, T.-S. 
Cao, T.-T.
Stephanus
Keywords: Computational geometry
GPGPU
Graphics hardware
Voronoi diagram
Issue Date: 2008
Source: Rong, G.,Tan, T.-S.,Cao, T.-T.,Stephanus (2008). Computing two-dimensional Delaunay triangulation using graphics hardware. Proceedings of the Symposium on Interactive 3D Graphics and Games, I3D 2008 : 89-97. ScholarBank@NUS Repository. https://doi.org/10.1145/1342250.1342264
Abstract: This paper presents a novel approach to compute, for a given point set S in ℝ 2, its Delaunay triangulation T (S). Though prior work mentions the possibility of using the graphics processing unit (GPU) to compute Delaunay triangulations, no known implementation and performance have been reported. Our work uncovers various challenges in the use of GPU for such a purpose. In practice, our approach exploits the GPU to assist in the computation of a triangulation T of S that is a good approximation to T (S). From that, the approach employs the CPU to transform T ' to T (S). As a major part of the total work is done by the GPU with parallel computing capability, it is a fast and practical approach, particularly for a large number of points (millions with the current state-of-the-art GPU). For such cases, our current implementation can run up to 53% faster on a Core2 Duo machine when compared to Triangle, the well-known fastest Delaunay triangulation implementation. Copyright © 2008 by the Association for Computing Machinery, Inc.
Source Title: Proceedings of the Symposium on Interactive 3D Graphics and Games, I3D 2008
URI: http://scholarbank.nus.edu.sg/handle/10635/42154
ISBN: 9781595939838
DOI: 10.1145/1342250.1342264
Appears in Collections:Staff Publications

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

SCOPUSTM   
Citations

35
checked on Dec 5, 2017

Page view(s)

67
checked on Dec 9, 2017

Google ScholarTM

Check

Altmetric


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