Pavages, fractions continues et géométrie discrète

-----------------------------------------
Une notion récurrente en combinatoire des mots est celle de mot
sturmien. Les mots sturmiens peuvent notamment être vus comme des
codages de droites discrètes. Dans ce cadre, des liens étroits ont
été mis en évidence entre le développement en fractions continues du
vecteur normal d'une droite discrète (c'est-à-dire le vecteur normal
de la droite réelle qui est discrétisée) et l'action de
transformations élémentaires - substitutions ou morphismes - sur les
mots sturmiens correspondants. En particulier, ces liens ont été
utilisés en géométrie discrète pour concevoir des algorithmes de
tracé ou de reconnaissance de droites discrètes, qui sont des
opérations fondamentales pour vectoriser des objets discrets.
Dans cette thèse, on s'intéresse à une possible généralisation de ces
liens en dimensions supérieures. Notons que plusieurs généralisations
multi-dimensionnelles des mots sturmiens, des fractions continues ou
des algorithmes de tracé et de segmentation de droites existent déjà.
Cependant, ces généralisations restent isolées, les liens existant
dans le cas unidimensionnel étant perdus. L'apport principal de cette
thèse est de proposer une généralisation englobant ces liens. Plus
précisément, on montre qu'une classe particulière de substitutions
agissant sur les pavages - qui jouent le rôle de mots multi-
dimensionnels - permet de calculer des développements de pavages,
généralisant les développement en fractions continues classique. Ceci
est notamment appliqué en géométrie discrète au tracé et à la
reconnaissance de plans discrets.
Soulignons qu'une des clefs essentielles de cette généralisation est
la notion de flip, venue de la mécanique statistique (par exemple
pour modéliser la formation des quasicristaux), et qui s'avère très
utile pour étudier l'action de substitutions sur des pavages.


----------