Computing Publications

Publications Home » Foundation of a Computable Solid ...

Foundation of a Computable Solid Modelling

Abbas Edalat, Lieutier

Journal Article
ACM Symposium on Solid Modeling and Applications, 1999
Theoretical Computer Science
Volume 284
Issue 2
pp.319–345
July, 2002
Elsevier
DOI 10.1016/S0304-3975(01)00091-3
Abstract

Solid modelling and computational geometry are based on classical topology and geometry in which the basic predicates and operations, such as membership, subset inclusion, union and intersection, are not continuous and therefore not computable. But a sound computational framework for solids and geometry can only be built in a framework with computable predicates and operations. In practice, correctness of algorithms in computational geometry is usually proved using the unrealistic Real RAM machine model of computation, which allows comparison of real numbers, with the undesirable result that correct algorithms, when implemented, turn into unreliable programs. Here, we use a domain-theoretic approach to recursive analysis to develop the basis of an effective and realistic framework for solid modelling. This framework is equipped with a well defined and realistic notion of computability which reflects the observable properties of real solids. The basic predicates and operations on solids are computable in this model which admits regular and non-regular sets and supports a design methodology for actual robust algorithms. Moreover, the model is able to capture the uncertainties of input data in actual CAD situations.

Author Keywords: Solid modelling; Robustness; Model of computation; Domain theory; Turing computability

Postscript of full publication (598 kilobytes)
(need help viewing Postscript files?)
BibTEX file for the publication
N.B.
Conditions for downloading publications from this site.
 

pubs.doc.ic.ac.uk: built & maintained by Ashok Argent-Katwala.