Foundation of a computable solid modelling.
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.
Introduction
Correctness of algorithms in computational geometry are usually proved using the Real RAM
machine [22] model of computation. Since this model is not realistic, correct algorithms, when
implemented, turn into unreliable programs. In CAGD modeling operators, the effect of rounding
errors on consistency and robustness of actual implementations is an open question, which is
handled in industrial software by various unreliable and expensive "up to epsilon" heuristics that
remain very unsatisfactory.
The authors claim that a robust algorithm is one whose correctness is proved with the assumption
of a realistic machine model [17, 18]. A branch of computer science, called recursive
analysis, defines precisely what it means, in the context of the realistic Turing machine model of
computation, to compute objects belonging to non-countable sets such as the real numbers.
In this paper, we use a domain-theoretic approach to recursive analysis to develop the basis
of an effective framework for solid modeling. The set-theoretic aspects of solid modeling is revis-
ited, leading to a theoretically motivated model that shows some interesting similarities with the
Requicha Solid Model [23, 24]. Within this model, some unavoidable limitations of solid modeling
computations are proved and a sound framework to design specifications for feasible modeling operators
is provided. Some consequences in computation with the boundary representation paradigm
are sketched that can incorporate existing methods [13, 28, 16, 14, 15] into a general, mathematically
well-founded theory. Moreover, the model is able to capture the uncertainties of input
data [8, 19] in actual CAD situations.
We need the following requirements for the mathematical model:
(1) the notion of computability of solids has to be well defined,
(2) the model has to reflect the observable properties of real solids,
(3) the model has to be closed under the Boolean operations,
(4) non-regular sets 1 have to be captured by the model as well,
(5) it has to support a design methodology for actual robust algorithms.
In Section 2, we outline some elements of recursive analysis and domain theory used in subsequent
sections. Section 3 presents the solid domain, a mathematical model for computable rigid solids.
In Section 4, we give an illustration, on a simple case, how one can design a robust algorithm in
the light of our domain-theoretic approach.
Recursive analysis and domain theory
In this section, we briefly outline some elements of recursive analysis [26, 7, 5, 21] and domain
theory [1, 29, 2] that we need in this paper. We first deal with N, the set of all non-negative
integers. A function f : N ! N, is recursive if it is computable by a general purpose computer
(e.g. a Turing machine or a C++ program); this means that there is a finite program written in
some general language such that its output is f(n) whenever its input is any n 2 N. A recursively
enumerable subset of N, or an r.e. set, is the image of a recursive function. A recursive set is
an r.e. set whose complement is also r.e. There are r.e. sets which are not recursive, but their
construction is non-trivial. Next, we consider the set Q of rational numbers. Since Q is countable,
it is in one-to-one correspondence with N and we can write
only if Therefore, computability over Q reduces to computability over N.
The theory of computability over the set of real numbers R, which is uncountable, is more
involved. Since the set of (finite) programs written in a general purpose computer is countable,
it follows that the set of computable real numbers, i.e. those which are the output of a finite
program, is also countable. These can be characterized in terms of recursive functions. A real
number r is computable if there exists recursive functions f and g such that
This means that r is the effective limit of a computable
sequence of rational numbers. We say that a real number is lower (respectively, upper) semi-
computable if it is the limit of an increasing (respectively, decreasing) computable sequence of
rational numbers. It then follows that a real number is computable if and only if it is lower and
upper semi-computable. Similarly, a function f : [a; b] ! R is computable if it is the effective
limit (in the sup norm) of a computable sequence of rational polynomials. Intuitively, in a suitable
representation such as the sign binary system, a real number is given by an infinite sequence of
digits and a computable function is one which can compute any finite part of the output sequence
by reading only a finite part of the input sequence. From this, it follows that a computable function
is always continuous with respect to the Euclidean topology of R.
Domain theory was originally introduced independently by Scott [27] as a mathematical theory
of semantics of programming languages and by Ershov [12] for studying partial computable functionals
of finite type. A domain is a structure for modeling a computational process or a data type
with incomplete or uncertain specified information. It is a partially ordered set where the partial
order corresponds to some notion of information. A simple example is the domain ftt; ff; ?g of the
Boolean values tt and ff together with a least element ? below both. One thinks of ? here as the
1 A set is regular if it the closure of its interior.
undefined Boolean value. A domain is also equipped with a notion of completion (as in Cauchy
completeness for metric spaces) and a notion of approximation. There is a so-called Scott topology
on a domain which is T 0 and is such that every open set is upward closed, i.e. whenever a Scott
open set contains an element, it also contains any element above that element. See the appendix
for precise definitions. A class of so-called !-continuous domains has in recent years been successfully
used in modeling computation in a number of areas of analysis [9]. An !-continuous domain
has a countable subset of basis elements such that every element of the domain can be completely
specified by the set of basis elements which approximate it. One can use this countable basis to
provide an effective structure for the domain and obtain the notions of a computable element of an
effectively given domain and of a computable function between two effectively given !-continuous
domains. We give two examples of useful continuous domains in this section which will motivate
the idea of the solid domain introduced in the next section.
The interval domain I[0; 1] n of the unit box [0; 1] n ae R n is the set of all non-empty n-dimensional
sub-rectangles in [0; 1] n ordered by reverse inclusion. A basic Scott open set is given,
for every open subset O of R n , by the collection of all rectangles contained in O. The map
x is an embedding onto the set of maximal elements of I[0; 1] n . Every
maximal element fxg can be obtained as the least upper bound (lub) of an increasing chain of
elements, i.e. a shrinking, nested sequence of sub-rectangles, each containing fxg in its interior
and thereby giving an approximation to fxg or equivalently to x. The set of sub-rectangles with
rational coordinates provides a countable basis. One can similarly define, for example, the interval
domain IR n of R n . For the interval domains I[\Gamma1; 1] and IR   , where R   is the one point
compactification of R, have been used to develop a feasible framework for exact real arithmetic
using linear fractional transformations [10, 20].
An important feature of domains, in the context of this paper, is that they can be used to obtain
computable approximations to operations which are classically non-computable. For example,
comparison of a real number with 0 is not computable. However, the function neg : I[\Gamma1;
neg([a; b]) =!
is the best computable approximation to this predicate.
The upper space UX of a compact metric space X is the set of all non-empty compact subsets
of X ordered by reverse inclusion. In fact, UX is a generalization of the interval domain and has
similar properties; for example a basic Scott open set is given, for every open subset O ae X , by the
collection of all non-empty compact subsets contained in O. As with the interval domain, the map
x is an embedding onto the set of maximal elements of UX . The upper
space gives rise to a computational model for fractals and for measure and integration theory [9].
The idea of the solid domain in the next section is closely linked with the upper space of [0; 1] n .
3 A domain-theoretic model
In this section, we introduce the solid domain, a mathematical model for representing rigid solids.
We focus here on the set-theoretic aspects of solid modeling as Requicha did in introducing the
r-sets model [23]. Our model is motivated by requirements (1) to (5) given in the introduction.
For any subset A of a topological space, A, A ffi , @A and A c denote respectively the closure, the
interior, the boundary and the complement of A. The regularization of a subset A is defined, by
Requicha [23, 24], as the subset A ffi . We say that a set is regular if it is equal to its regularization.
3.1 The solid domain
The solid domain S[0; 1] n of the unit cube [0; 1] n ae R n is the set of ordered pairs (A; B) of compact
subsets of [0; endowed with the information order:
. The elements of S[0; 1] n are called partial solids.
Proposition 3.1 (S[0; is a continuous domain and
Proposition 3.2 For any (A; B) 2 S[0; 1] n , there exists a subset Y of [0; 1] n such
One can take for example: We say that represents the
subset Y . It follows that the partial order S[0; 1] n is isomorphic with the quotient of the power
set of [0; 1] n under the equivalence relation with the ordering
Given any subset X of [0; 1] n , the classical membership predicate 2: [0; continuous
except on @X . It follows that the best continuous approximation of this predicate is
where the value ? is taken on @X (recall that any open set containing
? contains the whole set ftt; ff; ?g). Then, two subsets are equivalent if and only if they have
the same best continuous approximation of the membership predicate. By analogy with general
set theory for which a set is completely defined by its membership predicate, the solid domain
can be seen as the collection of subsets that can be distinguished by their continuous membership
predicates. The definition of the solid domain is then consistent with requirement (1) since a
computable membership predicate has to be continuous.
Our definition is also consistent with requirement (2) in a closely related way. We consider the
idealization of a machine used to measure mechanical parts. Two parts corresponding to equivalent
subsets cannot be discriminated by such a machine. Moreover, partial solids, and, more generally,
domain-theoretically defined data types (cf. Section allow us to capture partial, or uncertain
input data [8, 19] encountered in realistic CAD situations.
Starting with the continuous membership predicate, the natural definition for the complement
would be to swap the values tt and ff. This means that the complement of (A; B) is (B; A), cf.
requirement (3).
As for requirement (4), the figure below represents a subset X of [0; 1] 2 that is not regular. Its
regularization removes both the external and internal "dangling edge". This set can be captured in
our framework but not in the Requicha model. Here and in subsequent figures, the two components
A and B of the partial solid are depicted separately below each picture for clarity.
Proposition 3.3 The maximal elements of S[0; 1] n are precisely those that represent regular sets.
In other words, maximal elements are of the form (A; B) such that A and B are regular with
Next we consider the Boolean operators. We first note that the regularized union [23, 24]
of two adjacent three dimensional boxes (i.e. product of intervals) is not computable, since, to
decide whether the adjacent faces are in contact or not, one would have to decide the equality of
two real numbers which is not computable [21]. Requirements (1) and (3) entail the existence of
Boolean operators which are computable with respect to a realistic machine model (e.g. the Turing
machine).
A
In order to define Boolean operators on the solid domain, we obtain the truth table of logical
Boolean operators on ftt; ff; ?g. Consider the logical Boolean operator "or", which, applied to the
continuous membership predicates of two partial solids, would define their union.
This is indeed the truth table for parallel or in domain theory; see [2, page 133]. One can likewise
build the truth table for "and". Note the similarities with the (In,On,Out) points classifications
used in some boundary representation based algorithms [25, 3]. From these truth tables follow the
definition of Boolean operators on partial solids:
Beware that, given two partial solids representing adjacent boxes, their union would not represent
the set-theoretic union of the boxes, as illustrated in the figure below.
A 1o/oo A 2
We have defined the continuous membership predicate for points of [0; 1] n . In order to be able
to compute this predicate, we extend it to the interval domain I[0; 1] n by defining 2: I[0;
A
ff
A A
A A
Proposition 3.4 The following maps are continuous:
ffl 2: I[0;
Similarly, one can define the continuous predicate ae: S[0; ?g.
3.2 Computability on the solid domain
In order to endow S[0; 1] n with a computability structure, we introduce two different countable
bases that lead to the same notion of computability, but correspond to different types of algorithms
in use.
A rational hyperplane is a subset of R n of the form: f(x i
(0 are rational numbers such that at least one of them is non-zero. A rational polyhedron
is a regular subset of [0; 1] n whose boundary is included in a finite union of rational hyper-planes.
Notice that a rational polyhedron may not be connected and may also be the empty set. A dyadic
number is a rational number whose denominator is a power of 2. A dyadic voxel set is a finite
union of cubes, each the product of n intervals whose endpoints are dyadic numbers. Notice that
every voxel set is a rational polyhedra.
A partial rational polyhedron (PRP) is an element (A; B) 2 S[0; 1] n such that A and B are
rational polyhedra. In the following, PRP stands for the set of PRP's. A partial dyadic voxel set
(PDVS) is an element (A; B) 2 S[0; 1] n such that A and B are dyadic voxel sets. PDVS stands
for the set of PVDS's.
The set PRP is effectively enumerable, that is, each PRP can be represented by a finite set
of integers (i.e. the rational coordinates of the vertices and the incidence graph) and there exists
a program to compute a one to one correspondence between N and PRP so that we can write
\Deltag.
Proposition 3.5 PRP forms a countable basis for the solid domain S[0; 1] n . Moreover, the solid
domain is effectively given with respect to the enumeration fR 0 \Deltag of this basis.
Therefore: (i) every element of S[0; 1] n is the least upper bound of a sequence of PRP's approximating
it, and (ii) the predicate R k - R j is r.e. in k; j. In fact, this predicate is recursive, that is,
there exists a program able to decide, for any pair of integers k and j, whether or not R k - R j .
From a more practical point of view, this implies that the Boolean operators on rational polyhedra
are computable (see [6] for an efficient implementation), and that a subset is compact if and
only if it is the intersection of a countable set of rational polyhedra.
By the general notion of computability in domains (see the appendix), an element (A; B) 2
computable if the set fkjR k - (A; B)g is r.e. We obtain the same class of computable
partial solids if we replace the PRP basis with the PDVS basis.
Our notion of computability is somewhat weaker that one could expect. Consider a computable
partial solid (A; B) and a computable point x 2 [0; 1] n n A. There exists a program to compute
an increasing sequence converging to (A; B) and a program to compute an
increasing sequence I k of rational intervals of I[0; 1] n converging to x. From these two programs,
one can obtain a program to compute the increasing sequence of rational numbers representing the
square of the minimum distance between A k and I k . It follows that the minimum distance between
A and x is a lower semi-computable real number. However, this distance may not be computable.
We introduce a stronger notion of computability, that will make the above distance computable.
An element (A; B) 2 S[0; 1] n is recursive if the set fkjR k - (A; B)g is recursive. It can be shown [4]
that (A; B) is recursive if and only if there exists a program to compute two nested sequences of
rational polyhedra such that A and B are the effective limits of the sequences with respect to the
Hausdorff metric. In [4], several related notions of computability for compact sets are given. In
this setting, our notion of computable partial solid (A; B) means that A and B are co.r.e. and our
notion of recursive partial solid means that A and B are recursive. We have now a positive and a
negative result.
Proposition 3.6 The Boolean operators over S[0; 1] n are computable.
However, the intersection of two recursive partial solids may not be recursive as illustrated in
the figure below. The two initial recursive partial solids represent regular sets.
The details of construction of will be presented in the full version of the paper. The
crucial property is that the left endpoint of the lower horizontal line segment is the limit of a
computable, increasing, bounded sequence of rational numbers which is lower semi-computable
but not computable.
The intersection of A 1 and A 2 is therefore a horizontal segment whose left-end point is not
computable. Therefore, requirement(3) prevents us to choose recursive partial solids for our model.
A 1-A 2
However, we can choose the following notion which is stronger than computability but is neither
weaker nor stronger than recursiveness.
We say an element (A; B) 2 S[0; 1] n is Lebesgue computable if it is computable and if the
Lebesgue measures of A and B are computable. Note that
is the Lebesgue measure of C ae R n . Therefore, (A; B) is Lebesgue computable if and only if there
exists a program to compute an increasing sequence
and
Proposition 3.7 The Boolean operators over S[0; 1] n are Lebesgue computable. In other words,
there exists a program that, given two increasing sequences of PRP's defining two partial solids
such that their Lebesgue measures are effectively converging, computes an increasing sequence of
PRP's defining their intersection such that their Lebesgue measures is effectively converging.
A Lebesgue computable partial solid (A; B), with can be manufactured with
an error that can be made as small as we want in volume, assuming an idealized manufacturing
device.
The table below compares in general the three notions for computable solids.
Partial solid Distance to a point Boolean operators Lebesgues measure
computable semi-computable computable non-computable
recursive computable non-computable non-computable
Lebesgues computable semi-computable computable computable
At this stage of our work, our model of choice would be the Lebesgue computable partial solids,
since they are stable under Boolean operators.
4 Robustness Issues
We illustrate, on a very rudimentary class of boundary represented solids, how our domain-theoretic
approach matches requirement (5). Usually, robustness issues show up in two (related) way: (i)
A numerical computation is not well-specified in case of discontinuities, as for example in the
intersection of tangential, partially overlapping surfaces. (ii) The values of the logical predicates
evaluated from numerical computations are inconsistent, resulting in an invalid output or the
catastrophic failure of the algorithm.
4.1 The disk domain
We consider d, the set of disks in the Euclidean plane. Each disk a of d is represented by the three
real numbers giving the coordinates of the center and the radius: (x a ; y a ; R a ), with R a - 0. By an
abuse of notation, such an element a denotes both the real triple defining it and the corresponding
disk in the plane; the context always makes it clear which meaning we have in mind.
We now define the domain D of interval disks. It is the set of interval triples
with
K
K and
add the bottom element ? to D and partially
order it with reverse inclusion: K v L 3). The domain D is isomorphic
with its maximal elements can be identified with the elements of d. An element
is said to be rational if x \Gamma
K and R
K are rational numbers. ?From the
general theory of computability in domains (see the appendix), K is computable if it is the least
upper bound of an increasing computable sequence of rational interval disks, that is if there exists
a program to compute such an increasing sequence. This definition is consistent with the solid
domain introduced in Section 3 as we have the where the image f(K) of an
interval disk K 2 D is the partial solid
a
It can be easily shown that f is monotonic, continuous and in fact computable with respect to
the natural effective structure on D induced from I(R 2 \Theta R + ). When restricted to interval disks
contained in [0; 1] 2 , f is in fact an embedding.
4.2 The domain of the relative position of disks
We consider here the combinatorial part of the computation of Boolean operators over disks. For
this purpose we consider the following map from d \Theta d to R 3
and the predicates 3 from d \Theta d to the domain f\Gamma; +; ?g defined, for
0:
The domain topology on f\Gamma; +; ?g ensures that these predicates are continuous. Because of the
inequalities, the range of made of 11 values,
defining the relative position of the two disks. We denote this set of 11 values by F which is a
subset of the domain f\Gamma; +; ?g 3 , whose order relation, induced by the order relation on f\Gamma; +; ?g,
is represented in the figure below.
4.3 Extension to D and actual computation
We define the
Where inf denotes infimum or the greatest lower bound, which exists for every subset since F is
a bounded complete domain (see the appendix). P is the best continuous extension of p. It is
possible to compute the image P (K; L) of any pair (K; L) of rational interval disks, as this reduces
to the evaluation of the sign of a few polynomials over Q (see [6]). Then, from two increasing
sequences of rational interval disks (increasing with respect to v) defining a pair of interval disks,
one can compute an increasing sequence in F defining their relative position.
The actual image is computed after a finite time. However, when this image is not a maximal
element of F, one never knows if the output will be refined by using a more accurate input (i.e.
more terms from the two rational interval disk sequences). This behaviour is consistent with
requirement (2): in the physical world, the statement "two disks are tangent", for example, means
that there are tangent up to a relevant accuracy and a more accurate measuring may reveal that
they actually intersect or are in fact disjoint.
a b
a b
a b
a b
a b
a b
a b a
A# A#
A# A#A#A A#A
#A# A#A A
#A A
a b
A# A#A #A A# A#A# A#
a a
5 Conclusion
The solid domain described here satisfies the requirements of computability, having observable
properties, closure under Boolean operations, admission of non-regular sets and the design of robust
algorithms as stated in the introduction. The classical analysis framework, allowing discontinuous
behaviour and exact real number comparisons, is neither realistic as a model of our interaction with
the physical world (measuring, manufacturing), nor realistic as a basis for the design of algorithms
implemented on realistic machines, which are only able to deal with finite data. The authors believe
that the domain-theoretic approach, even at this initial stage of application to solid modeling and
computational geometry, is a powerful mathematical framework both to model partial or uncertain
data and to guide the design of robust software.
The solid model can be defined for a more general class of topological spaces, in particular for
locally compact Hausdorff spaces such as R n . It can also be represented equivalently in terms of
pairs of open sets or equivalently in terms of continuous functions from the space to the Boolean
domain ftt; ff; ?g. We will deal with these issues in a future paper.
In our future work, we will use the domain-theoretic framework to capture more information
on solids and geometric objects. In particular, we will deal more generally with the boundary representation
and the differential properties of curves and surfaces (that is the C k or G k properties).
We will also focus on actual computations, applying the methodology illustrated in Section 4 to
more complex situations.


Appendix


In this section, we give the formal definitions of a number of notions in domain theory used in the
paper. We think of a partially ordered set (poset) (P; v) as the set of output of some computation
such that the partial order is an order of information: in other words, a v b indicates that a has
less information than b. For example, the set f0; 1g 1 of all finite and infinite sequences of bits 0
and 1 with a v b if the sequence a is an initial segment of the sequence b is a poset and a v b
simply means that b has more bits of information than a. A non-empty subset A ' P is directed
if for any pair of elements there exists c 2 A such that a v c and b v c. A directed set
is therefore a consistent set of output elements of a computation: for every pair of output a and
b, there is some output c with more information than a and b. A directed complete partial order
(dcpo) or a domain is a partial order in which every directed subset D ' P has a least upper
bound (lub) denoted
F
A. It is easily seen that f0; 1g 1 is a dcpo. We say that a dcpo is pointed
if it has a least element which is usually denoted by ? and is called bottom.
For two elements a and b of a dcpo we say a is way-below or approximates b, denoted by a - b,
if for every directed subset A with b v
F
A there exists c 2 A with a v c. The idea is that
a is a finitary approximation to b: whenever the lub of a consistent set of output elements has
more information than b, then already one of the input elements in the consistent set has more
information than a. In f0; 1g 1 , we have a - b iff a v b and a is a finite sequence. The closed
subsets of the Scott topology of a domain are those subsets C which are downward closed (i.e.
closed under taking lub's of directed subsets (i.e. for every directed
subset A ' C we have
F
A 2 C).
A basis of a domain D is a subset B ' D such that for every element x 2 D of the domain
the set B fy 2 Bjy - xg of elements in the basis way-below x is directed with
F
An (!)-continuous domain is a dcpo with a (countable) basis. In other words, every element
of a continuous domain can be expressed as the lub of the directed set of basis elements which
approximate it. A domain is bounded complete if every bounded subset has a lub; in such a domain
every subset has an infimum or greatest lower bound. One can easily check that f0; 1g 1 is an
!-continuous dcpo for which the set of finite sequences form a countable basis. It can be shown
that a function f dcpo's is continuous with respect to the Scott topology if and
only if it is monotone (i.e. a v b ) f(a) v f(b)) and preserves lub's of directed sets i.e. for any
directed A ' D, we have f(
F
F
a2A f(a).
An !-continuous domain D with a least element ? is effectively given wrt an enumeration of
a countable base \Deltag with b if the set f! m;n is r.e., where
is the standard pairing function i.e. the isomorphism (x; y) 7! (x+y)(x+y+1)
This means that there is a master program which generates all pairs of basis elements (b
We say x 2 D is computable if the set fnjb n - xg is r.e. This is equivalent to say that
there is a recursive function g such that (b g(n) ) n-0 is an increasing chain in D with
F
We say that a continuous effectively given !-continuous domains D (with basis
computable if the set f! m;n ? jb m - f(an )g is
r.e. This is equivalent to say that f maps computable elements to computable elements in an
effective way. Every computable function can be shown to be a continuous function [30, Theorem
3.6.16]. It can be shown [11] that these notions of computability for the domain IR of intervals
of R induce the same class of computable real numbers and computable real functions as in the
classical theory [21] described in Section 2.

Acknowledgements

The first author has been supported by EPSRC and would like to thank the hospitality of the
Institute for Studies in Theoretical Physics and Mathematics in Tehran where part of this work
was done.



--R

Domain theory.
Domains and Lambda-Calculi
Toward a topology for computational geometry.
Computability on subsets of Euclidean space I: Closed and compact subsets.

Computing exact geometric predicates using modular arithmetic with single precision.
An Introduction to Recursive Function Theory.
Robustness of numerical methods in geometric computation when problem data is uncertain.
Domains for computation in mathematics
A new representation for exact real numbers.
A domain theoretic approach to computability on the real line.
Computable functionals of finite types.
Epsilon Geometry
Towards Robust Interval Solid Modeling of Curved Objects.
Robust interval algorithm for curve intersections.
Boundary Representation Modelling with local Tolerances.
Repr'esentation b.
Toward a data type for Solid Modeling based on Domain Theory.
Algorithmic tolerances and semantics in data exchange.
Efficient on-line computation of real functions using exact floating point
Computability in Analysis and Physics.
Computational Geometry: an introduction.
Mathematical Foundations of Constructive Solid Geometry
Representation for Rigid Solids
Boolean Operations in Solid Modeling: Boundary Evaluation and Merging Algorithms.

Outline of a mathematical theory of computation.
Using tolerances to guarantee valid polyhedral modeling results.
Mathematical Theory of Domains

--TR
Computational geometry: an introduction
Computability
Epsilon geometry: building robust algorithms from imprecise computations
Using tolerances to guarantee valid polyhedral modeling results
Dynamical systems, measures, and fractals via domain theory
Boundary representation modelling with local tolerances
Effective algebras
Domain theory
Towards robust interval solid modeling of curved objects
Algorithmic tolerances and semantics in data exchange
A domain-theoretic approach to computability on the real line
Foundation of a computable solid modeling
Domains and lambda-calculi
Computability on subsets of Euclidean space I
Computable banach spaces via domain theory
Representations for Rigid Solids: Theory, Methods, and Systems
Type Theory via Exact Categories
On The Measure Of Two-Dimensional Regions With Polynomial-Time Computable Boundaries

--CTR
Martin Ziegler, Effectively open real functions, Journal of Complexity, v.22 n.6, p.827-849, December, 2006
Abbas Edalat , Andr Lieutier, Domain theory and differential calculus (functions of one variable), Mathematical Structures in Computer Science, v.14 n.6, p.771-802, December 2004
solid modelling;robustness;domain theory;turing computability;model of computation