Proof of correctness of the digital Delaunay triangulation algorithm Journal Article


Author(s): Cao, Thanh-Tung; Edelsbrunner, Herbert; Tan, Tiow Seng
Article Title: Proof of correctness of the digital Delaunay triangulation algorithm
Affiliation IST Austria
Abstract: We prove that the dual of the digital Voronoi diagram constructed by flooding the plane from the data points gives a geometrically and topologically correct dual triangulation. This provides the proof of correctness for recently developed GPU algorithms that outperform traditional CPU algorithms for constructing two-dimensional Delaunay triangulations.
Keywords: computational geometry; Graphics processing unit; GPU; digital geometry; parallel computation; CUDA; OpenCL
Journal Title: Computational Geometry: Theory and Applications
Volume: 48
Issue 7
ISSN: 0925-7721
Publisher: Elsevier  
Date Published: 2015-08-01
Start Page: 507
End Page: 519
Sponsor: Supported by NSF under grant DBI-0820624 and by DARPA under grants HR011-05-1-0057 and HR0011-09-0065.
DOI: 10.1016/j.comgeo.2015.04.001
Open access: no
IST Austria Authors
Related IST Austria Work