Vous êtes ici : GIPSA-lab > Formation > Thèses soutenues
Chargement
DESPRE Vincent

Topologie et algorithmes sur les cartes combinatoires

 

Co-directeur de thèse :     Francis LAZARUS

École doctorale : Mathématiques, sciences et technologies de l'information, informatique (mstii)

Spécialité : Informatique

Structure de rattachement : UJF

Établissement d'origine : UNIVERSITE LYON 1

Financement(s) : Contrat doctoral

 

Date d'entrée en thèse : 01/09/2013

Date de soutenance : 18/10/2016

 

Composition du jury :
FRANCIS LAZARUS,Directeru de thèse,GIPSA-LAB
ANDRAS SEBO,Directeur de thèse,G-SCOP
XAVIER GOAOC,Rapporteur,UNIVERSITE PARIS-EST - MARNE LA VALLEE
STEFAN FELSNER,Rapporteur,UNIVERSITE TECHNIQUE DE BERLIN - ALLEMAGNE
OLIVIER DEVILLERS,Examinateur,INRIA DELEGATION NANCY GRAND EST
NICOLAS BONICHON,Examinateur,UNIVERSITE DE BORDEAUX
STEPHAN THOMASS,Examinateur,ECOLE NORMALE SUPERIEURE DE LYON
SERGIO CABELLO,Examinateur,UNIVERSITE DE LJUBLJANA - SLOVENIE

 

Résumé : Dans cette thèse, nous nous intéressons aux propriétés topologiques des surfaces, i.e. celles qui sont préservées par des déformations continues. Intuitivement, ces propriétés peuvent être imaginées comme étant celles qui décrivent la forme générale des surfaces. Nous utilisons des cartes combinatoires pour décrire les surfaces. Elles ont le double avantage d’être des objets mathématiques naturels et de pouvoir être transformées en structure de données. Nous étudions trois problèmes différents. Premièrement, nous donnons des algorithmes de calcul du nombre géométrique d’intersection de courbes dessinées sur des surfaces. Nous avons obtenu: un algorithme quadratique de calcul du nombre minimal d’auto-intersections dans une classe d’homotopie, un algorithme quartique pour construire un représentant minimal et un algorithme quasi-linéaire pour déterminer si une classe d’homotopie contient bien une courbe simple. Nous donnons ensuite des contre-exemples à la conjecture de Mohar et Thomassen traitant de l’existence de cycles de partage dans les triangulations. Finalement, nous utilisons les travaux récents de Lévèque et Gonçalves à propos des bois de Schnyder toriques pour construire une bijection entre les triangulations du tore et certaines cartes unicellulaires analogues à la célèbre bijection de Poulalhon et Schaeffer pour les triangulations


GIPSA-lab, 11 rue des Mathématiques, Grenoble Campus BP46, F-38402 SAINT MARTIN D'HERES CEDEX - 33 (0)4 76 82 71 31