Please use this identifier to cite or link to this item:
Title: Computing two-dimensional Delaunay triangulation using graphics hardware
Authors: Rong, G.
Tan, T.-S. 
Cao, T.-T.
Keywords: Computational geometry
Graphics hardware
Voronoi diagram
Issue Date: 2008
Citation: 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.
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
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.


checked on Dec 10, 2018

Page view(s)

checked on Dec 8, 2018

Google ScholarTM



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