Challenges and Issues in Robust Geometric Computation

Chen Li.
Talk to be presented at the DIMACS Workshop on "Algorithmic and Quantitative Aspects of Real Algebraic Geometry in Mathematics and Computer Science" , March 12-16, 2001.

ABSTRACT: In the last two decades, research in computational geometry has produced an impressive wealth of efficient algorithms. But the rate of technology transfer to applications lags behind. One important reason for this is the well-known numerical non-robustness problem that often arises in the implementation of algorithms.

In this talk, I will survey recent research efforts in robust geometric computation. My main focus will be on the challenges and issues in Exact Geometric Computation (EGC), a general approach for removing non-robustness. The main issue in EGC is efficiency and various techniques have been proposed. An example is the computation of effective root bounds. I will describe some of our theoretical as well as experimental efforts. We have developed an easy-to-use C++ library called the Core Library to make EGC techniques widely available to programmers. An unexpected application of this library is in automated proving of elementary geometry theorems.