Computing Publications

Publications Home » Computability of Partial Delaunay...

Computability of Partial Delaunay Triangulation and Voronoi Diagram

Ali Khanban, Abbas Edalat, Lieutier

Conference or Workshop Paper
CCA 2002, Computability and Complexity in Analysis (ICALP 2002 Satellite Workshop)
July, 2002
Electronic Notes in Theoretical Computer Science
Volume 66
Issue 1
DOI 10.1016/S1571-0661(04)80381-5

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.

GZipped Postscript of full publication (468 kilobytes)
(need help viewing GZipped Postscript files?)
BibTEX file for the publication
Conditions for downloading publications from this site. built & maintained by Ashok Argent-Katwala.