Title: Theory of Real Computation According to EGC
Speaker: Chee Yap, NYU
Date: April 11, 2006 2:00-3:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
The Exact Geometric Computation (EGC) mode of computation has been developed over the last decade in response to the widespread problem of numerical non-robustness in geometric algorithms. Today, it is one of the most successful approaches for solving such problems. Its theory and techniques are encoded in libraries such as LEDA, CGAL and Core Library. The key feature of EGC is the necessity to decide zero in its computation.
In this talk, we consider the computational foundation for the EGC mode of computation. This is evidently based on a theory of real computation. Two dominant approaches here are (1) The Analytic School [Grzegocyzk, Weihrauch, Ko]. (2) The Algebraic School [Theoretical algorithms, Blum-Shub-Smale]. Neither of these theories are not suitable for capturing the key feature of EGC: the zero problem is undecidable in (1) and trivial in (2).
We propose an alternative approach based on real approximation. The basic results of this theory will be described, initially in terms of the standard Turing model of computation. To adequately model semi-numerical problems such as found in computational geometry, we adapt Schoenhage's pointer machines to serve as a Numerical Computational Model (which is equivalent to Turing model). We prove a Transfer Theorem characterizing when semi-numerical problems, solvable in the algebraic model, are actually computable in the numerical model.