Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates

Exact computer arithmetic has a variety of uses, including the robust implementation of geometric algorithms. This article has three purposes. The first is to offer fast software-level algorithms for exact addition and multiplication of arbitrary precision floating-point values. The second is to propose a technique for adaptive precision arithmetic that can often speed these algorithms when they are used to perform multiprecision calculations that do not always require exact arithmetic, but must satisfy some error bound. The third is to use these techniques to develop implementations of several common geometric calculations whose required degree of accuracy depends on their inputs. These robust geometric predicates are adaptive; their running time depends on the degree of uncertainty of the result, and is usually small.

These algorithms work on computers whose floating-point arithmetic uses radix two and exact rounding, including machines complying with the IEEE 754 standard. The inputs to the predicates may be arbitrary single or double precision floating-point numbers. C code is publicly available for the two-dimensional and three-dimensional orientation and incircle tests, and robust Delaunay triangulation using these tests. Timings of the implementations demonstrate their effectiveness.

Authors and Affiliations

1. School of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213, USA jrs@cs.cmu.edu, , , , , , US

   Jonathan Richard Shewchuk

Received May 16, 1996, and in revised form March 10, 1997.

Reprints and permissions