TITLE:
Subdivision Algorithms and Integral Analysis.

Chee K. Yap

Invited Talk
MACIS 2007 - International Conf. on
	Mathematical Aspects of Computer and Information Sciences
Paris, France, December 5-7, 2007


ABSTRACT:
Geometric operations on curves and surfaces can be
based on algebraic approaches
(e.g., cylindrical algebraic decomposition, resultants)
or on numerical/geometric approaches
(e.g., subdivision methods, interval methods).
We focus on the latter approaches as they are
practical, easy to implement and has adaptive complexity.
But such algorithms are rarely complete.

We describe some current work in providing
complete and adaptive algorithms for isotopic approximations of
implicit curves.  In particular, we describe a
complete subdivision algorithm that can treat singular curves.
This extends the recent work of Plantinga-Vegter.

Then we address the complexity analysis
of such algorithms.  For this, we consider the
one-dimensional analogue of approximating curves;
the algorithm now amounts to 
real root isolation via evaluation-based subdivision.
We provide a novel integral analysis of the complexity
of the non-singular case of algorithm.