Exact Geometric Computation and Beyond
Chee Yap ( Courant Institute of Mathematical Sciences, New York University (visiting Oxford) )
Exact Geometric Computation (EGC) has been developed over the last 15 years by computational geometers in response to the widespread problem of numerical non-robustness in geometric algorithms. It is currently the most successful approach to non-robustness, and its technology has been encoded in libraries such as LEDA, CGAL and Core Library. The unique requirement of EGC is the necessity to decide zero in its computation. The zero problem arises in many challenging problems such as surface intersection in geometric modeling, meshing of implicit surfaces with guaranteed topology, determination of singularity and automated geometric theorem proving. Current theories of real computation (viz., computable analysis, algebraic real computation, numerical analysis) do not treat the zero problem adequately, and hence do not account for the empirical work that supports EGC. We outline some key features of a suitable theory. In this introductory talk, I will first give a brief overview of EGC, then survey recent results and describe on-going challenges.