Adaptive Precision Floating-Point Arithmetic and Fast Robust Predicates for Computational Geometry

Jonathan Richard Shewchuk
Computer Science Division
University of California at Berkeley
Berkeley, California 94720-1776
Created as part of the Archimedes project (tools for parallel finite element methods).
Supported in part by NSF Grant CMS-9318163 and an NSERC 1967 Scholarship.
Many computational geometry applications use numerical tests known as the orientation and incircle tests. The orientation test determines whether a point lies to the left of, to the right of, or on a line or plane defined by other points. The incircle test determines whether a point lies inside, outside, or on a circle defined by other points.

Each of these tests is performed by evaluating the sign of a determinant (see the figure below). The determinant is expressed in terms of the coordinates of the points. If these coordinates are expressed as single or double precision floating-point numbers, roundoff error may lead to an incorrect result when the true determinant is near zero. In turn, this misinformation can lead an application to fail or produce incorrect results.

One way to solve this problem is to use exact arithmetic. Unfortunately, traditional libraries for arbitrary precision floating-point arithmetic are quite slow, and can reduce the speed of an application by one or two orders of magnitude.

To minimize this problem, I've produced algorithms and implementations for performing the 2D and 3D orientation and incircle tests correctly and reasonably quickly. From this page, you may access papers describing the approach (short and long versions), and the code itself. My hope is that working computational geometers will be able to simply plug the code into their applications with little effort, and forget about robustness problems (for those algorithms that only require orientation and incircle tests).

My algorithms are faster than traditional arbitrary precision libraries for two reasons. First, I use an unusual approach to exact arithmetic, pioneered by Douglas Priest and sped by me, that has its greatest advantage over traditional techniques when manipulating numbers of relatively small complexity (a few hundred or thousand bits). Second, the algorithms are adaptive in the sense that they do only as much work as necessary to guarantee a correct result. The sign of a small determinant can typically be determined quickly unless the determinant is close to zero. See the papers for details.

Papers

The long version. The short version. Covers the most important points, but leaves out all the proofs and many details. Presents a slower version of the addition algorithm because there wasn't room to explain the fastest one.

Software

Inspiration

Also check out the corresponding papers and software offered by Avnaim, Boissonnat, Devillers, Preparata, and Yvinec. Their technique may be faster than mine (I haven't timed theirs), but is meant for points whose coordinates are integers.
Jonathan Shewchuk