Calcul effectif de la topologie de courbes et surfaces algébriques réelles
Institution:
LimogesDisciplines:
Abstract EN:
In this thesis, we got interested into the Effective Computation of the Topology of Real Algebraic Curves and Surfaces. One can distinguish three main new algorithms in the field of shape representation. Our first algorithm is a certified symbolic-numerical based on sub-resultants properties and computes the topology of a plane algebraic curve with the best known complexity. The second algorithms computes the topology of a space curve defined as the intersection of two implicit algebraic surfaces. For the designing of this algorithm, we introduce the notion of space curve in pseudo-generic position with respect to a given plane. This approach leads to a certified symbolic-numerical algorithm with the best known complexity. The third algorithms is a new and complete one for computing the isotopic meshing of an implicit algebraic surface. It involves only subresultant computations and entirely relies on rational manipulation, which makes it direct to implement. Finally, we also design an algorithm for computing the cells in an arrangement of quadrics which may be classify on the area of configuration spaces computation.
Abstract FR:
Ce travail de thèse relève du registre de l’algorithmique de courbes et surfaces algébriques réelles. Dans le domaine de la représentation de formes nous avons développé trois algorithmes. Le premier est un algorithme symbolique-numérique certifié, fortement basé sur les propriétés des sous-résultants, et permettant le calcul de la topologie d’une courbe algébrique plane avec la meilleure complexité connue. Le deuxième algorithme traite le problème du calcul de la topologie d’une courbe algébrique spatiale définie comme intersection de deux surfaces algébriques implicites. Pour construire cet algorithme, nous avons introduit la notion de courbe spatiale en position pseudo-générique par rapport à un plan. Cette approche conduit à un algorithme symbolique-numérique certifié disposant de la meilleure complexité connue pour traiter ce problème. Le troisième est un algorithme de maillage de surfaces implicites. C’est le premier algorithme certifié et implémenté qui résoud le problème du maillage isotopique de surfaces implicites singulières. Soulignons que ce travail rentre aussi dans le cadre des applications mathématiques puisqu’on peut, à partir d’une triangulation, calculer de nombreux invariants topologiques. Enfin dans un travail sur les arrangements pouvant se placer dans le cadre des problèmes de configurations spatiales, nous évoquons un algorithme permettant le calcul d’un tel arrangement.