---
_id: '1578'
abstract:
- lang: eng
  text: 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.
acknowledgement: "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\r\n"
article_processing_charge: No
author:
- first_name: Thanhtung
  full_name: Cao, Thanhtung
  last_name: Cao
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: Tiowseng
  full_name: Tan, Tiowseng
  last_name: Tan
citation:
  ama: Cao T, Edelsbrunner H, Tan T. Triangulations from topologically correct digital
    Voronoi diagrams. <i>Computational Geometry</i>. 2015;48(7):507-519. doi:<a href="https://doi.org/10.1016/j.comgeo.2015.04.001">10.1016/j.comgeo.2015.04.001</a>
  apa: Cao, T., Edelsbrunner, H., &#38; Tan, T. (2015). Triangulations from topologically
    correct digital Voronoi diagrams. <i>Computational Geometry</i>. Elsevier. <a
    href="https://doi.org/10.1016/j.comgeo.2015.04.001">https://doi.org/10.1016/j.comgeo.2015.04.001</a>
  chicago: Cao, Thanhtung, Herbert Edelsbrunner, and Tiowseng Tan. “Triangulations
    from Topologically Correct Digital Voronoi Diagrams.” <i>Computational Geometry</i>.
    Elsevier, 2015. <a href="https://doi.org/10.1016/j.comgeo.2015.04.001">https://doi.org/10.1016/j.comgeo.2015.04.001</a>.
  ieee: T. Cao, H. Edelsbrunner, and T. Tan, “Triangulations from topologically correct
    digital Voronoi diagrams,” <i>Computational Geometry</i>, vol. 48, no. 7. Elsevier,
    pp. 507–519, 2015.
  ista: Cao T, Edelsbrunner H, Tan T. 2015. Triangulations from topologically correct
    digital Voronoi diagrams. Computational Geometry. 48(7), 507–519.
  mla: Cao, Thanhtung, et al. “Triangulations from Topologically Correct Digital Voronoi
    Diagrams.” <i>Computational Geometry</i>, vol. 48, no. 7, Elsevier, 2015, pp.
    507–19, doi:<a href="https://doi.org/10.1016/j.comgeo.2015.04.001">10.1016/j.comgeo.2015.04.001</a>.
  short: T. Cao, H. Edelsbrunner, T. Tan, Computational Geometry 48 (2015) 507–519.
date_created: 2018-12-11T11:52:49Z
date_published: 2015-08-01T00:00:00Z
date_updated: 2025-09-29T10:58:50Z
day: '01'
department:
- _id: HeEd
doi: 10.1016/j.comgeo.2015.04.001
external_id:
  isi:
  - '000355887700001'
intvolume: '        48'
isi: 1
issue: '7'
language:
- iso: eng
month: '08'
oa_version: None
page: 507 - 519
publication: Computational Geometry
publication_status: published
publisher: Elsevier
publist_id: '5593'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Triangulations from topologically correct digital Voronoi diagrams
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 48
year: '2015'
...