Item

Abstract

This work presents novel geometric algorithms dealing with algebraic curves and
surfaces of arbitrary degree. These algorithms are exact and complete � they
return the mathematically true result for all input instances. Efficiency is
achieved by cutting back expensive symbolic computation and favoring
combinatorial and adaptive numerical methods instead, without spoiling
exactness in the overall result.
We present an algorithm for computing planar arrangements induced by real
algebraic curves.We show its efficiency both in theory by a complexity
analysis, as well as in practice by experimental comparison with related
methods. For the latter, our solution has been implemented in the context of
the Cgal library. The results show that it constitutes the best current exact
implementation available for arrangements as well as for the related
problem of computing the topology of one algebraic curve. The algorithm is also
applied to related problems, such as arrangements of rotated curves, and
arrangments embedded on a parameterized surface.
In R3, we propose a new method to compute an isotopic triangulation of an
algebraic surface. This triangulation is based on a stratification of the
surface, which reveals topological and geometric information. Our
implementation is the first for this problem that makes consequent use of
numerical methods, and still yields the exact topology of the surface.
The thesis is written in English.