UNIVERSITÉ PARIS DENIS DIDEROT UFR D'INFORMATIQUE

Eric Colin De Verdiere

Description

Niveau: Supérieur, Doctorat, Bac+8
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 Shortening of curves and decomposition of surfaces Examining board : M. Christian Choffrut (Univ. Paris 7) president Mme Christiane Frougny (Univ. Paris 8) examiner M. Michel Pocchiola (ENS Paris) thesis advisor M. Günter Rote (FU Berlin) reviewer Mme Marie-Françoise Roy (Univ. Rennes 1) reviewer Mme Brigitte Vallée (CNRS & Univ. Caen) examiner Other rewiever : M. Herbert Edelsbrunner (Duke Univ.) Research done in the Laboratoire d'informatique de l'École normale supérieure UMR 8 548 du CNRS

• really grateful


• marie-françoise roy


• ecole normale


• over all


• roy


• all members


• discussion can

Sujets

• Le Bihan
• Vallée
• Floater
• Denise

Informations

• Publié par: profil-zyak-2012
• Publié le: 01 décembre 2003
• Nombre de lectures: 19
• Langue: English
• 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
Shortening of curves
and decomposition of surfaces
Examining board :
Research done in theM. Christian Choffrut (Univ. Paris 7) president
Laboratoire d’informatique
Mme Christiane Frougny (Univ. Paris 8) examiner
de l’ cole normale supØrieure
M. Michel Pocchiola (ENS Paris) thesis advisor
M. G nter Rote (FU Berlin) reviewer
Mme Marie-Fran oise Roy (Univ. Rennes 1)er
Mme Brigitte VallØe (CNRS & Univ. Caen) examiner
Other rewiever : UMR 8 548 du CNRS
M. Herbert Edelsbrunner (Duke Univ.)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
Shortening of curves
and decomposition of surfaces
Examining board :
Research done in theM. Christian Choffrut (Univ. Paris 7) president
Laboratoire d’informatique
Mme Christiane Frougny (Univ. Paris 8) examiner
de l’ cole normale supØrieure
M. Michel Pocchiola (ENS Paris) thesis advisor
M. G nter Rote (FU Berlin) reviewer
Mme Marie-Fran oise Roy (Univ. Rennes 1)er
Mme Brigitte VallØe (CNRS & Univ. Caen) examiner
Other rewiever : UMR 8 548 du CNRS
M. Herbert Edelsbrunner (Duke Univ.)2
The thesis was originally written in French, except Chapters 4 and 5, which are
also in English in the original version. This document is a translation by the
author.
Errors and typos might have been introduced during the translation (or even
exist in the French version). If you nd such errors, I would really appreciate the
feedback.3
Acknowledgements
I would like to thank rst Michel Pocchiola, who guided and encouraged me during
these three years of thesis. He was able to propose interesting research topics, to
improve my ability in writing, and to give me adequate advices when I needed
help. I particularly appreciated his help when writing this document.
I thank Jacques Stern, the headmaster of the Computer Science Department
at ENS. Many thanks also to Jacques Beigbeder, Kilian Hart, and Catherine Le
Bihan, maintaining a high-quality computer installation, to Joºlle Isnard, Michelle
Angely, Jean-Claude Denise, and ValØrie Mongiat for their availability and e -
ciency in the necessary administrative tasks, and to the team of the library.
I would like to say my gratitude to Herbert Edelsbrunner, G nter Rote, and
Marie-Fran oise Roy, reviewers of this thesis; I thank them for the interest they
expressed in reading my work. Thanks also to Christian Cho rut, Christiane
Frougny, and Brigitte VallØe, who accepted to be in my examining board.
Many thanks also to Jean-Daniel Boissonnat and to all members of the Prisme
team for their kindness during the few visits I did at Inria Sophia-Antipolis. I ap-
preciated to work with Mariette Yvinec on conforming Delaunay triangulations.
Thanks to David Cohen-Steiner, with whom every discussion can generate new
ideas, and to Pierre Alliez, who always knows how to relate theory and applica-
tions.
I would like to thank also the other researchers with whom I had the privilege
and the pleasure to work, in particular Gert Vegter, who initiated my learning
in mathematical writing, and Francis Lazarus, who also read my work on Tutte’s
theorem.
Let me also thank, for many reasons, several persons for their help: my uncle
Yves Colin de VerdiŁre, Robert Connelly, Michael Floater, ValØrie Pham-Trong,
Michael Starbird, and Anne Verroust.
I wish to thank the persons I met everyday during this thesis, and whose help
was precious. Thanks to those who shared with me the o ce of the students of
the team: Pierre Angelier, Xavier Goaoc, and Laurent Rineau, who helped me in
programming, and Luc Habert, newcomer in the team.
I am really grateful to my family, wife’s family, and friends who encouraged
me and helped to make these years enjoyable. Finally and over all, thanks to
Mathilde for her priceless help and her support, particularly when I was writing
this thesis.4 Acknowledgements5
Contents
Introduction 9
1 Topology of surfaces 13
1.1 Surfaces, curves and graphs embeddings . . . . . . . . . . . . . . . 13
1.1.1 Surfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.1.2 Curves, connectivity, and the Jordan Sch n ies theorem . . 14
1.1.3 Graphs and embeddings of graphs . . . . . . . . . . . . . . 15
1.2 Polyhedral surfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.2.1 De nition and properties . . . . . . . . . . . . . . . . . . . 16
1.2.2 Cutting surfaces . . . . . . . . . . . . . . . . . . . . . . . . 17
1.3 Classi cation and decomposition of surfaces . . . . . . . . . . . . . 18
1.3.1 Topological invariants . . . . . . . . . . . . . . . . . . . . . 18
1.3.2 Classi cation theorem and polygonal schemata . . . . . . . 20
1.3.3 Pants decompositions . . . . . . . . . . . . . . . . . . . . . 25
1.4 Homotopy, isotopy, and universal covering space . . . . . . . . . . . 26
1.4.1 Homotopy . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
1.4.2 Isotopy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
1.4.3 A few simple results . . . . . . . . . . . . . . . . . . . . . . 28
1.4.4 Universal covering space . . . . . . . . . . . . . . . . . . . . 28
2 Previous works 33
2.1 Computation of shortest paths . . . . . . . . . . . . . . . . . . . . 33
2.1.1 Shortest paths in graphs . . . . . . . . . . . . . . . . . . . . 34
2.1.2 paths in a planar region . . . . . . . . . . . . . . . 35
2.1.3 Shortest paths on polyhedral surfaces . . . . . . . . . . . . 36
2.2 Curves on surfaces: homotopy and decomposition . . . . . . . . . . 37
2.2.1 Surface decomposition . . . . . . . . . . . . . . . . . . . . . 38
2.2.2 Contractibility and homotopy tests . . . . . . . . . . . . . . 40
2.2.3 Uncrossing curves . . . . . . . . . . . . . . . . . . . . . . . . 44
2.3 Homotopic shortest paths . . . . . . . . . . . . . . . . . . . . . . . 46
2.3.1 Smooth surfaces . . . . . . . . . . . . . . . . . . . . . . . . 47
2.3.2 Flat surfaces . . . . . . . . . . . . . . . . . . . . . . . . . 49
2.3.3 The case of the plane . . . . . . . . . . . . . . . . . . . . . . 49
2.4 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
2.4.1 Applications of shortest paths . . . . . . . . . . . . . . . . . 50
2.4.2 of short cuttings of surfaces . . . . . . . . . . . 516 CONTENTS
2.4.3 Applications of shortest homotopic paths . . . . . . . . . . 54
Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
3 Optimization of curves on surfaces 57
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.1 Framework of the study . . . . . . . . . . . . . . . . . . . . . . . . 60
3.1.1 De nition of length . . . . . . . . . . . . . . . . . . . . . . . 60
3.1.2 Particular case of a polyhedral surface . . . . . . . . . . . . 61
3.2 Optimization theorems for cut systems . . . . . . . . . . . . . . . . 62
3.2.1 Cut systems by graph . . . . . . . . . . . . . . . . . . . . . 63
3.2.2 Cut by cycles . . . . . . . . . . . . . . . . . . . . . 66
3.2.3 Variations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
3.3 Proofs of the optimization theorems for cut systems . . . . . . . . . 68
3.3.1 Crossing words . . . . . . . . . . . . . . . . . . . . . . . . . 68
3.3.2 Proof of Theorem 3.2 . . . . . . . . . . . . . . . . . . . . . . 71
3.3.3 Proof of 3.7 . . . . . . . . . . . . . . . . . . . . . . 77
3.4 Extension of an embedding to a cut system . . . . . . . . . . . . . 86
3.4.1 Cut systems by graph . . . . . . . . . . . . . . . . . . . . . 87
3.4.2 Cut by cycles . . . . . . . . . . . . . . . . . . . . . 89
3.5 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
3.5.1 Combinatorial curves . . . . . . . . . . . . . . . . . . . . . . 90
3.5.2 Algorithmic study of a shortening operation . . . . . . . . . 94
3.5.3 Complexity of the optimization algorithms . . . . . . . . . . 97
3.5.4 Extension to a cut system . . . . . . . . . . . . . . . . . . . 98
Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
Appendix: Exponential cost of the na ve optimization method . . . . . . 111
4 Tutte’s barycenter method applied to isotopies 113
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
4.1 Proof of Tutte’s theorem . . . . . . . . . . . . . . . . . . . . . . . . 116
4.1.1 Proof of the theorem in a special case . . . . . . . . . . . . 117
4.1.2 The general case . . . . . . . . . . . . . . . . . . . . . . . . 119
4.2 Isotopies in the plane . . . . . . . . . . . . . . . . . . . . . . . . . . 122
4.3 Generalization to 3D space . . . . . . . . . . . . . . . . . . . . . . 128
4.4 Appendix: The strict convex hull . . . . . . . . . . . . . . . . . . . 132
4.5 Appendix: Invertibility of Sy