Computing Publications

Publications Home » Computability in Computational Geometry

Computability in Computational Geometry

Abbas Edalat, Ali Khanban, Lieutier

Conference or Workshop Paper
New Computational Paradigms: First Conference on Computability in Europe, CiE 2005, Amsterdam, The Netherlands
June, 2005
Lecture Notes in Computer Science
Volume 3526
ISBN 3-540-26179-6
ISSN 0302-9743
DOI 10.1007/11494645_15

We promote the concept of object directed computability in computational geometry in order to faithfully generalise the well-established theory of computability for real numbers and real functions. In object directed computability, a geometric object is computable if it is the effective limit of a sequence of finitary objects of the same type as the original object, thus allowing a quantitative measure for the approximation. The domain-theoretic model of computational geometry provides such an object directed theory, which supports two such quantitative measures, one based on the Hausdorff metric and one on the Lebesgue measure. With respect to a new data type for the Euclidean space, given by its non-empty compact and convex subsets, we show that the convex hull, Voronoi diagram and Delaunay triangulation are Hausdorff and Lebesgue computable.

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