Our Goal:
Robust geometric algorithms via Exact Computation 
Robust implementation of geometric algorithms is difficult to achieve. Many researchers have devised methods to address this problem within the framework of fixedprecision arithmetic. We believe that nonrobustness of geometric algorithms is inherent when one is committed to fixedprecision, and the best general policy for attacking nonrobustness is the ``exact computation''. 


Geometric Structure = Combinatorial Structure + Numerical Quantities  We first clarify the nature of geometric computing. Geometric algorithms characteristically involve geometric structures which involves a combinatorial structure (such as a graph) with associated numerical quantities (such a numerical values labeling the nodes and edges). Moreover, there are consistency constraints governing the relation between the combinatorial structure and numerical quantities. This means that perturbing the numerical values without taking into account the combinatorial structure can lead to qualitatively different or inconsistent states, which may result in catastrophic errors in algorithms. Geometric algorithms may involve either the construction of, or searching in, geometric structures. 


Exact Geometric Computation  Exact computation has a naive interpretation, namely, to compute every numerical quantity exactly. This surely guarantees the robustness of algorithms. But computing irrational numbers ``exactly'' needs suitable interpretation. Even in the rational case, it is too inefficient. We shall interpret exact geometric computing to mean computations in which numerical quantities are computed to sufficient precision so that the underlying combinatorial structure is mathematically exact. 


Precisiondriven Approach to Exact Implementation  We introduce the precisiondriven approach to exact geometric computation. Assume the computation or algorithm amounts to the repeated evaluation of algebraic expressions. For each expression, we assume that some à priori bound of the necessary precision can be determined. For instance, if we often only need to know the sign of an expression, and amounts to approximating its value relative precision of 1bit. This à priori precision can then be propagated to other parts of the computation, at run time, so that precision is locally adaptive. 


Expr realizes PrecisionDriven Computation 
As a tool for the above precisiondriven approach to
exact geometric computation, we implement the Expr package for
the class of constructible real numbers, namely, real expressions over the operators
sqrt() .
(i) the class BigFloat with automatic errorbound propagation, (ii) the extendible class Real that encompasses a variety of real number representations. 


Use in Exact Geometric Computation  The Real/Expr package is sufficient for the exact implementation of most of algorithms in contemporary computational geometry. Real/Expr is useful for exact computation because many fundamental predicates of geometric algorithms can be represented by real constructible expressions. For example, "P is left of the directed line segment QR (directed from Q to R) is expressed as a sign of a suitable determinant constructed from P, Q, R. We construct the corresponding Real/Expr expression for this determinant and approximate its value to one relative bit of precision to get its (errorfree) sign. 