Computing with Real Numbers Ⅰ. The LFT Approach to Real Number Computation Ⅱ. A Domain Framework for Computational Geometry

摘要

We introduce, in Part Ⅰ, 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 Ⅱ, 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.