We introduce a new data type in a new model of geometric computation, which is based on computability theory and supports the design of robust algorithms for exact real number input as well as for input with uncertainty, i.e. imprecise or partial input. In this framework imprecisely given points as input to an algorithm are represented by convex polygons and the output of the algorithm produces two open subsets as the interior and the exterior of a partially defined geometric ob ject. It is the distinguished feature of this model that all basic predicates and operations such as membership, union and intersection are computable and the algorithms developed in this framework are inherently robust. We develop algorithms for the convex hull, Voronoi diagram and Delaunay triangulation in this model, which while robust have the complexity of the corresponding classical algorithms. Furthermore, in this framework one can define the notion of a computable geometric ob ject and for the first time show that the convex hull, Voronoi diagram and Delaunay triangulation are indeed computable operations in the sense of recursion theory.
pubs.doc.ic.ac.uk: built & maintained by Ashok Argent-Katwala.