Topology of real algebraic curves and projection of real analytic surfaces.
Topologie de courbes algébriques planes et projection de surfaces analytiques réelles.
Résumé
The topic of this thesis is related to algorithmic geometry. We focus on the problem to built algo- rithms that give a representation of the topology for geometric sets defined implicitly. We got two main results : The fisrt one deals with the real algebraic curve. Given a real plan algebraic curve VR(P) defined as the zero set of a square free polynomial P ∈ Z[X,Y] of magnitude (d,τ), our algorithm computes straight planar graph isotopic to VR(P) using only O ̃(d5τ+d6) bit operations and without putting the curve in generic position. Note that, Mehlhorn et al. deal with the same problem, but their algorithm start by a random process to get a generic position of the curve. The second main result of this thesis is an algorithm that computes the graph of singularites of a real analytic surface Ω ⊂ R3. Let M be a surface in R4 defined as the intersection of two hypersurfaces, Ω is then defined as the image of M by the canonical projection from R4 to R3. Usually, the surface Ω is not smooth. We give an algorithm that computes a graph isotopic to the set of singularities of Ω, which is required to reconstruct the whole topology of Ω.
Cette thèse traite de la représentation topologique d’objets géométriques définis de façon implicite. La résolution de ce type de problème relève du domaine de la géométrie algorithmique. Soit VR(P) une courbe algébrique réelle plane définie comme étant le lieu des zéros d’un poly- nôme sans facteur carré P ∈ Z[X,Y] de magnitude (d,τ). Le premier résultat principal présenté dans ce manuscrit est un algorithme qui calcule un complexe simplicial isotope à VR(P) sans pas- ser par une mise en position générique de VR(P) avec seulement O ̃(d5τ+d6) opérations binaires. Il constitue une alternative à l’algorithme de Mehlhorn et al., dont le succès repose sur un processus aléatoire de détermination d’une position générique de VR(P). La deuxième contribu- tion principale de cette thèse est un algorithme permettant de calculer le graphe des singularités d’une surface analytique réelle Ω ⊂ R3 : étant donnée une surface analytique réelle lisse M défi- nie comme une intersection de deux hypersurfaces réelles dans R4, la surface Ω est l’image de M par la projection canonique de R4 dans R3. La surface Ω comporte, en général, des singularités. Le calcul du graphe des singularités apparait donc comme un problème sous-jacent dans l’étape de la reconstruction de la topologie globale de Ω.
Origine : Fichiers produits par l'(les) auteur(s)