Adaptive Precision Floating-Point Arithmetic
and Fast Robust Geometric Predicates
Jonathan Richard Shewchuk
School of Computer Science
Carnegie Mellon University
Pittsburgh, Pennsylvania 15213
Exact computer arithmetic has a variety of uses including, but not limited to,
the robust implementation of geometric algorithms. This report 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 one wishes to perform multiprecision
calculations that do not always require exact arithmetic, but must satisfy
some error bound. The third is to provide a practical demonstration of these
techniques, in the form of 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 2D and
3D orientation and incircle tests, and robust Delaunay triangulation using
these tests. Timings of the implementations demonstrate their effectiveness.
Discrete & Computational Geometry 18(3):305-363, October 1997. (Available here
as Technical Report CMU-CS-96-140, School of Computer Science, Carnegie Mellon
University, Pittsburgh, Pennsylvania, May 1996.)
Paper available through the URL
http://www.cs.cmu.edu/~quake-papers/robust-arithmetic.ps
For additional details and associated software, see the Web page
http://www.cs.cmu.edu/~quake/robust.html
BibTeX entry:
@article{shewchuk97a,
author = {Jonathan Richard Shewchuk},
title = {Adaptive {P}recision {F}loating-{P}oint {A}rithmetic and {F}ast
{R}obust {G}eometric {P}redicates},
journal = {Discrete \& Computational Geometry},
volume = 18,
number = 3,
pages = {305--363},
month = oct,
year = 1997
}