UNIVERSITÉ PARIS DENIS DIDEROT UFR D'INFORMATIQUE

Eric Colin De Verdiere

Description

Niveau: Supérieur

• redaction


• mémoire

UNIVERSITÉ PARIS 7 — DENIS DIDEROT UFR D'INFORMATIQUE THÈSE présentée et soutenue publiquement le 8 décembre 2003 pour l'obtention du Diplôme de Docteur de l'Université Paris 7 Spécialité : Algorithmique par Éric Colin de Verdière Raccourcissement de courbes et décomposition de surfaces Membres du jury : M. Christian Choffrut (Univ. Paris 7) président Mme Christiane Frougny (Univ. Paris 8) examinatrice M. Michel Pocchiola (ENS Paris) directeur de thèse M. Günter Rote (FU Berlin) rapporteur Mme Marie-Françoise Roy (Univ. Rennes 1) rapporteuse Mme Brigitte Vallée (CNRS et Univ. Caen) examinatrice Autre rapporteur : M. Herbert Edelsbrunner (Univ. Duke) Recherches effectuées au Laboratoire d'informatique de l'École normale supérieure UMR 8 548 du CNRS

• tri- angulations de delaunay conformes


• équipe de la bibliothèque


• apprentissage de la rédaction mathématique


• bureau des thésards de l'équipe


• source d'idées nouvelles

Sujets

• Redaction
• Mémoire
• Mathématiques
• Le Bihan
• Vallée

Informations

• Publié par: profil-nechor-2012
• Publié le: 01 décembre 2003
• Nombre de lectures: 110
• Langue: Français
• Poids de l'ouvrage: 1 Mo

Extrait

UNIVERSIT PARIS 7 DENIS DIDEROT
UFR D’INFORMATIQUE
TH¨SE
prØsentØe et soutenue publiquement
le 8 dØcembre 2003
pour l’obtention du Dipl me de
Docteur de l’UniversitØ Paris 7
SpØcialitØ : Algorithmique
par
ric Colin de VerdiŁre
Raccourcissement de courbes
et dØcomposition de surfaces
Membres du jury :
Recherches e ectuØes auM. Christian Choffrut (Univ. Paris 7) prØsident
Laboratoire d’informatique
Mme Christiane Frougny (Univ. Paris 8) examinatrice
de l’ cole normale supØrieure
M. Michel Pocchiola (ENS Paris) directeur de thŁse
M. G nter Rote (FU Berlin) rapporteur
Mme Marie-Fran oise Roy (Univ. Rennes 1) rapporteuse
Mme Brigitte VallØe (CNRS et Univ. Caen) examinatrice
Autre rapporteur : UMR 8 548 du CNRS
M. Herbert Edelsbrunner (Univ. Duke)UNIVERSIT PARIS 7 DENIS DIDEROT
UFR D’INFORMATIQUE
TH¨SE
prØsentØe et soutenue publiquement
le 8 dØcembre 2003
pour l’obtention du Dipl me de
Docteur de l’UniversitØ Paris 7
SpØcialitØ : Algorithmique
par
ric Colin de VerdiŁre
Raccourcissement de courbes
et dØcomposition de surfaces
Membres du jury :
Recherches e ectuØes auM. Christian Choffrut (Univ. Paris 7) prØsident
Laboratoire d’informatique
Mme Christiane Frougny (Univ. Paris 8) examinatrice
de l’ cole normale supØrieure
M. Michel Pocchiola (ENS Paris) directeur de thŁse
M. G nter Rote (FU Berlin) rapporteur
Mme Marie-Fran oise Roy (Univ. Rennes 1) rapporteuse
Mme Brigitte VallØe (CNRS et Univ. Caen) examinatrice
Autre rapporteur : UMR 8 548 du CNRS
M. Herbert Edelsbrunner (Univ. Duke)23
Remerciements
Je tiens ? remercier tout d’abord Michel Pocchiola, qui m’a guidØ et encouragØ
durant ces trois annØes de thŁse. Il a su me proposer des sujets de recherche
intØressants, me faire progresser dans l’art de la rØdaction et me prodiguer ses
conseils quand le besoin s’en faisait sentir. J’ai particuliŁrement apprØciØ son aide
lors de la rØdaction de ce mØmoire.
Je remercie Jacques Stern, qui m’a accueilli au sein du laboratoire d’informa-
tique de l’ENS. Ma reconnaissance s’adresse aussi ? Jacques Beigbeder, Kilian
Hart et Catherine Le Bihan, qui maintiennent un service informatique de qualitØ,
? Joºlle Isnard, Michelle Angely, Jean-Claude Denise et ValØrie Mongiat pour
leur disponibilitØ et leur e cacitØ dans les nØcessaires t ches administratives, et
? l’Øquipe de la bibliothŁque.
Je tiens ? exprimer toute ma reconnaissance ? Herbert Edelsbrunner, G nter
Rote et Marie-Fran oise Roy, rapporteurs de cette thŁse. Qu’ils soient remerciØs
pour l’intØrŒt qu’ils ont portØ ? mon travail. Merci Øgalement ? Christian Cho rut,
Christiane Frougny et Brigitte VallØe d’avoir acceptØ de siØger dans mon jury de
soutenance.
Ma gratitude s’adresse Øgalement ? Jean-Daniel Boissonnat et ? tous les
membres de l’Øquipe Prisme pour leur accueil lors de mes quelques visites ? l’In-
ria Sophia-Antipolis. J’ai apprØciØ de travailler avec Mariette Yvinec sur les tri-
angulations de Delaunay conformes. Merci ? David Cohen-Steiner, dont chaque
conversation est source d’idØes nouvelles, et ? Pierre Alliez, qui sait si bien faire
le lien entre thØorie et applications.
Je voudrais aussi remercier les autres chercheurs avec lesquels j’ai eu la chance
et le plaisir de travailler, en particulier Gert Vegter, qui a initiØ mon apprentissage
de la rØdaction mathØmatique, et Francis Lazarus, qui a aussi relu mon travail
sur le thØorŁme de Tutte.
Qu’il me soit aussi permis de remercier, ? des titres variØs, diverses personnes
pour leur aide : mon oncle Yves Colin de VerdiŁre, Robert Connelly, Michael
Floater, ValØrie Pham-Trong, Michael Starbird et Anne Verroust.
Je souhaite aussi remercier les personnes que j’ai c toyØes durant cette thŁse,
et dont l’aide a ØtØ prØcieuse. Merci ? ceux qui ont partagØ avec moi le bureau
des thØsards de l’Øquipe : Pierre Angelier, Xavier Goaoc et Laurent Rineau, qui
m’ont aidØ en programmation, et Luc Habert, arrivØ rØcemment.
Je suis tout particuliŁrement reconnaissant envers tous ceux, famille, belle-
famille et amis, qui m’ont encouragØ et ont contribuØ ? rendre ces annØes agrØables.
En n et surtout, merci ? Mathilde pour son aide inestimable et son soutien,
particuliŁrement lors de la rØdaction de cette thŁse.4 Remerciements5
Table des matiŁres
Introduction 9
1 Topologie des surfaces 15
1.1 Surfaces, courbes et plongements de graphes . . . . . . . . . . . . . 15
1.1.1 Surfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.1.2 Courbes, connexitØ et thØorŁme de Jordan Sch n ies . . . . 16
1.1.3 Graphes et plongements de graphes . . . . . . . . . . . . . . 17
1.2 Surfaces polyØdrales . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.2.1 DØ nition et propriØtØs . . . . . . . . . . . . . . . . . . . . . 18
1.2.2 DØcoupage de surfaces . . . . . . . . . . . . . . . . . . . . . 19
1.3 Classi cation et dØcomposition des surfaces . . . . . . . . . . . . . 20
1.3.1 Invariants topologiques . . . . . . . . . . . . . . . . . . . . . 20
1.3.2 ThØorŁme de classi cation et schØmas polygonaux . . . . . 22
1.3.3 DØcompositions en pantalons . . . . . . . . . . . . . . . . . 27
1.4 Homotopie, isotopie et revŒtement universel . . . . . . . . . . . . . 28
1.4.1 Homotopie . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
1.4.2 Isotopie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
1.4.3 Quelques rØsultats simples . . . . . . . . . . . . . . . . . . . 30
1.4.4 RevŒtement universel . . . . . . . . . . . . . . . . . . . . . . 30
2 Travaux antØrieurs 35
2.1 Calculs de plus courts chemins . . . . . . . . . . . . . . . . . . . . 35
2.1.1 Plus courts chemins dans les graphes . . . . . . . . . . . . . 36
2.1.2 Plus c dans un domaine du plan . . . . . . . . 37
2.1.3 Plus courts chemins sur des surfaces polyØdrales . . . . . . . 38
2.2 Courbes sur des surfaces : homotopie et dØcomposition . . . . . . . 39
2.2.1 DØcomposition de surfaces . . . . . . . . . . . . . . . . . . . 40
2.2.2 Tests de contractibilitØ et d’homotopie . . . . . . . . . . . . 42
2.2.3 DØcroisement de courbes . . . . . . . . . . . . . . . . . . . . 47
2.3 Plus courts chemins homotopes . . . . . . . . . . . . . . . . . . . . 49
2.3.1 Les surfaces lisses . . . . . . . . . . . . . . . . . . . . . . . . 50
2.3.2 Le cas des surfaces planes . . . . . . . . . . . . . . . . . 52
2.3.3 Le cas du plan . . . . . . . . . . . . . . . . . . . . . . . . . 52
2.4 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
2.4.1 Applications des plus courts chemins . . . . . . . . . . . . . 53
2.4.2 des dØcoupages de surface courts . . . . . . . . 546 TABLE DES MATI¨RES
2.4.3 Applications des calculs de plus courts chemins homotopes . 57
Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
3 Optimisation de courbes sur des surfaces 61
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.1 Cadre de l’Øtude . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
3.1.1 DØ nition de la longueur . . . . . . . . . . . . . . . . . . . . 64
3.1.2 Cas particulier d’une surface polyØdrale . . . . . . . . . . . 65
3.2 ThØorŁmes d’optimisation de systŁmes de dØcoupage . . . . . . . . 66
3.2.1 SystŁmes de dØcoupage par graphe . . . . . . . . . . . . . . 67
3.2.2 de par cycles . . . . . . . . . . . . . . . 70
3.2.3 Variantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
3.3 DØmonstration des thØorŁmes d’optimisation . . . . . . . . . . . . . 72
3.3.1 Mot des croisements . . . . . . . . . . . . . . . . . . . . . . 72
3.3.2 DØmonstration du thØorŁme 3.2 . . . . . . . . . . . . . . . . 75
3.3.3 du 3.7 . . . . . . . . . . . . . . . . 82
3.4 ComplØtion en un systŁme de dØcoupage . . . . . . . . . . . . . . . 92
3.4.1 SystŁmes de dØcoupage par graphe . . . . . . . . . . . . . . 92
3.4.2 de par cycles . . . . . . . . . . . . . . . 94
3.5 Algorithmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
3.5.1 Courbes combinatoires . . . . . . . . . . . . . . . . . . . . . 96
3.5.2 tude algorithmique d’une opØration de raccourcissement . 99
3.5.3 ComplexitØ des algorithmes d’optimisation . . . . . . . . . . 102
3.5.4 ComplØtion en un systŁme de dØcoupage . . . . . . . . . . . 104
Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
Annexe : Coßt exponentiel de la mØthode d’optimisation na ve . . . . . 116
4 MØthode barycentrique de Tutte appliquØe aux isotopies 119
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
4.1 Proof of Tutte’s theorem . . . . . . . . . . . . . . . . . . . . . . . . 122
4.1.1 Proof of the theorem in a special case . . . . . . . . . . . . 123
4.1.2 The general case . . . . . . . . . . . . . . . .