# 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

points.

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

3D.

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.

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

points.

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

3D.

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.