Computability of Partial Delaunay Triangulation and Voronoi Diagram [Extended Abstract]

AbstractUsing 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