New Methods for Computing the Topology of Algebraic Curves and Surfaces

Wednesday, May 30, 2007 - 9:00am - 9:50am
EE/CS 3-180
Bernard Mourrain (Institut National de Recherche en Informatique Automatique (INRIA))
Computing the topology of a geometric object defined implicitly appears in
many geometric modeling problems, such as surface-surface intersection,
self-intersection, arrangement computation problems ...
It is a critical step in the analysis and approximation of (semi-)algebraic
curves or surfaces, encountered in these geometric operations.

Its difficulties are mainly due to the presence of singularities on these
algebraic objects and to the analysis of the geometry near these singular

The classical approach which has been developed for algebraic curves
in the plane projects the problem onto a line, detects the value which are
critical for this projection and lift points back on the curve at these
critical values and in between. Information on the number of branches at
these critical values or genericity condition tests on the number of critical
points above a value of the projection have to be computed, in order to be
able to perform correctly the combinatorial connection step of these
algorithms. This approach has also been extended to curves and surfaces in

In the talk, we will consider methods which requires information on the
boundary of regions instead of information at critical points. We will
describe a new method for computing the topology of planar implicit curves,
which proceed by subdivision and which only requires the isolation of
extremal points. Extension of this approach to curves and surfaces in 3D will
be described. Experimentation of these algorithms based on the subdivision
solvers of the library SYNAPS and the algebraic-geometric modeler AXEL will
shortly demonstrated.