Automatic generation of staged geometric predicates

Algorithms in Computational Geometry and Computer Aided Design are often de veloped for the Real RAM model of computation, which assumes exactness of a ll the input arguments and operations. In practice, however, the exactness imposes tremendous limitations on the algorithms - even the basic operation s become uncomputable, or prohibitively slow. When the computations of inte rest are limited to determining the sign of polynomial expressions over flo ating-point numbers, faster approaches are available. One can evaluate the polynomial in floating-point first, together with some estimate of the roun ding error, and fall back to exact arithmetic only if this error is too big to determine the sign reliably. A particularly efficient variation on this approach has been used by Shewchuk in his robust implementations of Orient and InSphere geometric predicates. We extend Shewchuk's method to arbitrary polynomial expressions. The expres sions are given as programs in a suitable source language featuring basic a rithmetic operations of addition, subtraction, multiplication and squaring, which are to be perceived by the programmer as exact. The source language also allows for anonymous functions, and thus enables the common functional programming technique of staging. The method is presented formally through several judgments that govern the compilation of the source expression int o target code, which is then easily transformed into SML or, in case of sin gle-stage expressions, into C.