Computability of Partial Delaunay Triangulation and Voronoi Diagram
File(s)
Accepted version
Author(s)
Khanban, A
Edalat, A
Lieutier t, A
Type
Conference Paper
Abstract
Using the domain-theoretic model for geometric computation, we define the partial Delaunay triangulation and the partial Voronoi diagram of N partial points in R2 and show that these operations are domain-theoretically computable and effectively computable with respect to Hausdorff distance and Lebesgue measure. These results are obtained by showing that the map which sends three partial points to the partial disc passing through them is computable. This framework supports the design of robust algorithms for computing the Delaunay triangulation and the Voronoi diagram with imprecise input.\r\n
Version
Accepted version
Date Issued
2002-07
Citation
Electronic Notes in Theoretical Computer Science, 2002, 66 (1), pp.91-103
ISSN
1571-0661
Publisher
Elsevier
Source Title
CCA 2002, Computability and Complexity in Analysis (ICALP 2002 Satellite Workshop)
Conference
Electronic Notes in Theoretical Computer Science
Start Page
91
End Page
103
Journal / Book Title
Electronic Notes in Theoretical Computer Science
Volume
66
Issue
1
Copyright Statement
© 2002 Published by Elsevier B.V. NOTICE: this is the author’s version of a work that was accepted for publication in Electronic Notes in Theoretical Computer Science. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, VOL:66, ISSUE:1, (2002) DOI:10.1016/S1571-0661(04)80381-5
Source Place
Malaga, Spain
Coverage Spatial
Malaga, Spain