Seminars

Isotopic Arrangement of Curves: an Exact Numerical Approach, 
by Vikram Sharma (IMS Chennai)


Description :
-------------

Computing good approximations to curves and surfaces is a fundamental problem in nonlinear computational geometry.
In this talk, we describe a new subdivision algorithm for computing an isotopic approximation of a curve arrangement. 
We assume the curve arrangement is ``simple'' in the sense that no three curves have a common intersection, any two
 curves intersect transversally, and each curve is non-singular.
A curve is given as the zero set of an analytic function $f:\RR^2\to\RR^2$,
and effective interval forms of $f, \pdiff{f}{x}, \pdiff{f}{y}$ are available. Our solution generalizes the isotopic
curve approximation algorithms of Plantinga-Vegter (2004)and Lin-Yap (2009). In contrast to the typical 
exact algorithms in this area, we do not use algebraic techniques such as resultants or algebraic 
manipulation, such as shearing. Our subdivision approach is based on numerical primitives, with certification 
provided by interval methods. Such algorithms have many favorable properties: they are practical, easy to implement, 
suffer no implementation gaps, have adaptive and local complexity.
This is based on joint work with Gert Vegter and Chee Yap.