We introduce, in Part I, a number representation suitable for exact real number computation, consisting of an exponent and a mantissa, which is an infinite stream of signed digits, based on the interval [-1,1]. Numerical operations are implemented in terms of linear fractional transformations (LFT's). We derive lower and upper bounds for the number of argument digits that are needed to obtain a desired number of result digits of a computation, which imply that the complexity of LFT application is that of multiplying n-bit integers. In Part II, we present an accessible account of a domain-theoretic approach to computational geometry and solid modelling which provides a data-type for designing robust geometric algorithms, illustrated here by the convex hull algorithm.
[Paper.ps.gz (72p, 360k)]
Two pages on one (without scaling!): [Paper.ps.gz (36p, 360k)] for A4 paper, [Paper.ps.gz (36p, 360k)] for Letter paper.
Reinhold Heckmann /