Foundation of a computable toplology for solid modelling
by
Abbas Edalat
Department of Computing, Imperial College, London
Coauthors: Andre Lieutier

Computational geometry and solid modelling are based, on the one hand, on classical notions of topology and, on the other hand, on the Real RAM (Random Access Machine) model of computation. These foundations, which are classically consistent, are both unsatisfactory in any feasible computational framework. In fact, the basic predicates and operations in topology, such as the classical membership predicate of a proper subset of the Euclidean space or the binary operation of intersection of, say, compact subsets, are in general discontinuous and, therefore, non-computable. Furthermore, the Real RAM model is unrealistic since it assumes that comparison of real numbers is decidable in finite time. Consequently, classically correct algorithms in computational geometry and solid modelling, when implemented for actual computation, turn into unreliable programs which can crash. We present a domain, equipped with its Scott topology, to model the space of solid objects. In this model, all the basic predicates and operations, such as the membership predicate and the intersection operator, are indeed continuous. This framework is equipped with a well-defined and realistic notion of computability which reflects the observable properties of real solids. It admits regular and non-regular sets, and supports a design methodology for reliable (robust) algorithms. Moreover, the model is able to capture the uncertainties of input data in actual CAD situations.

Date received: July 20, 1999