Triangulations from topologically correct digital Voronoi diagrams Journal Article


Author(s): Cao, Thanhtung; Edelsbrunner, Herbert; Tan, Tiowseng
Article Title: Triangulations from topologically correct digital Voronoi diagrams
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: GPU; digital geometry; Delaunay triangulation; GPGPU
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: The research of the first and the third author is partially supported by NUS under grant R-252-000-337-112. The research of the second author is partially supported by NSF under grant DBI-0820624 and by DARPA under grants HR011-05-1-0057 and HR0011-09-006
DOI: 10.1016/j.comgeo.2015.04.001
Notes: We would like to thank the anonymous reviewer for the valuable feedback to improve the paper.
Open access: no
IST Austria Authors
Related IST Austria Work