@device(postscript)
@libraryfile(Mathematics10)
@libraryfile(Accents)
@style(fontfamily=timesroman,fontscale=11)
@pagefooting(immediate, left "@c<Technical Report 1996>",
center "@c<Computer Science>",
right "@c<Carnegie Mellon>")
@heading(Adaptive Precision Floating-Point Arithmetic
and Fast Robust Geometric Predicates)
@heading(CMU-CS-96-140)
@center(@b(Jonathan R. Shewchuk))
@center(May 1996)
@center(FTP: CMU-CS-96-140.ps)
@blankspace(1)
@begin(text)

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.

@blankspace(2line)
@begin(transparent,size=10)
@b(Keywords:@ )@c<Arbitrary precision floating-point arithmetic, computational
geometry, geometric robustness, orientation test, incircle test,
Delaunay triangulation>
@end(transparent)
@blankspace(1line)
@end(text)
@flushright(@b[(59 pages)])