Computing Publications

Publications Home » Computational Geometry with Impre...

Computational Geometry with Imprecise Input Data

Abbas Edalat, Ali Khanban, Lieutier

Research Monograph
December, 2005

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.

GZipped Postscript of full publication (260 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.