### DIMACS Theoretical Computer Science Seminar

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.