Higher-Order and Symbolic Computation, 16(4)379-400
Automatic Generation of Staged Geometric PredicatesAleksandar Nanevski, Carnegie Mellon University
Guy Blelloch, Carnegie Mellon University
Robert Harper, Carnegie Mellon University
|
Abstract: Algorithms in Computational Geometry and Computer
Aided Design are often developed for the Real RAM model of
computation, which assumes exactness of all the input arguments and
operations. In practice, however, the exactness imposes tremendous
limitations on the algorithms -- even the basic operations become
uncomputable, or prohibitively slow. In some important cases,
however, the computations of interest are limited to determining the
sign of polynomial expressions. In such circumstances, a faster
approach is available: one can evaluate the polynomial in
floating-point first, together with some estimate of the rounding
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 expressions are given as programs in a suitable source language featuring basic arithmetic 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; the use of such functions enables the common functional programming technique of staging. The method is presented formally through several judgments that govern the compilation of the source expression into target code, which is then easily transformed into SML or, in case of single-stage expressions, into C. Keywords: robust predicates, floating-point filters, exact arithmetic, program transformation, computational geometry |
This article can be downloaded [here].
![[picture of journal cover]](../LISP.JPG)