Robustness in Computational Geometry
Jonathan Richard Shewchuk
Computer Science Division
University of California at Berkeley
I survey the basic difficulties and approaches to robust implementations
of algorithms in computational geometry. Geometric computing differs from
traditional numerical computing because inconsistencies between different
geometric tests are the main means by which roundoff error makes geometric
programs crash. Hardness results in geometric realizability imply that
some computations more or less require exact arithmetic. Thus I discuss
methods for making exact arithmetic fast, including floating-point
filters, extended precision arithmetic, and separation bounds.
--
Bio: Jonathan Shewchuk is an Associate Professor in the Department of
Electrical Engineering and Computer Sciences at UC Berkeley. He is best
known for his software Triangle for high-quality triangular mesh
generation, which won the 2003 James Hardy Wilkinson Prize in Numerical
Software, and his "Introduction to the Conjugate Gradient Method Without
the Agonizing Pain."