Proof of correctness of the digital Delaunay triangulation algorithm

T. Cao, H. Edelsbrunner, T. Tan, Computational Geometry: Theory and Applications 48 (2015) 507–519.

Download
No fulltext has been uploaded. References only!

Journal Article | Published | English
Author
; ;
Department
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.
Publishing Year
Date Published
2015-08-01
Journal Title
Computational Geometry: Theory and Applications
Acknowledgement
Supported by NSF under grant DBI-0820624 and by DARPA under grants HR011-05-1-0057 and HR0011-09-0065.
Volume
48
Issue
7
Page
507 - 519
IST-REx-ID

Cite this

Cao T, Edelsbrunner H, Tan T. Proof of correctness of the digital Delaunay triangulation algorithm. Computational Geometry: Theory and Applications. 2015;48(7):507-519. doi:10.1016/j.comgeo.2015.04.001
Cao, T., Edelsbrunner, H., & Tan, T. (2015). Proof of correctness of the digital Delaunay triangulation algorithm. Computational Geometry: Theory and Applications, 48(7), 507–519. https://doi.org/10.1016/j.comgeo.2015.04.001
Cao, Thanh, Herbert Edelsbrunner, and Tiow Tan. “Proof of Correctness of the Digital Delaunay Triangulation Algorithm.” Computational Geometry: Theory and Applications 48, no. 7 (2015): 507–19. https://doi.org/10.1016/j.comgeo.2015.04.001.
T. Cao, H. Edelsbrunner, and T. Tan, “Proof of correctness of the digital Delaunay triangulation algorithm,” Computational Geometry: Theory and Applications, vol. 48, no. 7, pp. 507–519, 2015.
Cao T, Edelsbrunner H, Tan T. 2015. Proof of correctness of the digital Delaunay triangulation algorithm. Computational Geometry: Theory and Applications. 48(7), 507–519.
Cao, Thanh, et al. “Proof of Correctness of the Digital Delaunay Triangulation Algorithm.” Computational Geometry: Theory and Applications, vol. 48, no. 7, Elsevier, 2015, pp. 507–19, doi:10.1016/j.comgeo.2015.04.001.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar