Structure des pavages, droites discrètes 3D et combinatoire des mots

Labbé, Sébastien (2012). « Structure des pavages, droites discrètes 3D et combinatoire des mots » Thèse. Montréal (Québec, Canada), Université du Québec à Montréal, Doctorat en mathématiques.

Fichier(s) associé(s) à ce document :

Prévisualisation	PDF Télécharger (27MB)

Résumé

Cette thèse, constituée d'une série d'articles, considère des questions issues de la géométrie discrète en les traitant du point de vue de la combinatoire des mots qui s'avère un outil puissant et approprié pour les résoudre. Nous utilisons les mots soit pour représenter un chemin dans Z2 ou Z3, soit pour coder la suite des virages d'un chemin ou le contour d'une figure discrète fermée. Parmi les thèmes abordés, on compte les pavages du plan par polyominos, la notion de complexité en facteurs palindromes et la génération de droites discrètes 3D. La première partie concerne les pavages du plan où nous étudions le nombre de pavages réguliers du plan par une tuile carrée, c'est-à-dire une tuile ayant quatre tuiles adjacentes identiques. Il s'avère que certaines tuiles carrées pavent le plan de deux façons distinctes et elles sont appelées doubles carrées. Nous démontrons d'abord qu'il y a au plus deux tels pavages réguliers par une tuile carrée. Ensuite, nous considérons deux familles particulières de tuiles doubles carrées : les tuiles de Christoffel et les tuiles de Fibonacci. Ces deux familles décrivent les plus petits exemples de tuiles doubles carrées et peuvent être définies à partir des mots de Christoffel et du mot de Fibonacci par des règles de substitution et de concaténation. Les tuiles de Fibonacci définissent aussi une fractale, obtenue par un chemin auto-évitant, dont nous avons calculé plusieurs statistiques, comme le rapport de l'aire de la fractale sur l'aire de son enveloppe convexe. Dans l'article suivant, nous démontrons que tout double carré indécomposable est invariant sous une rotation de 180 degrés. Cette propriété géométrique est équivalente au fait que le mot de contour de la tuile se factorise en un produit de palindromes. Notre preuve repose sur une méthode de génération exhaustive des tuiles doubles carrées. La deuxième partie concerne la complexité palindromique - le nombre de facteurs palindromes distincts -, un sujet propre à la combinatoire des mots. Nous y considérons quatre classes de complexité palindromique qui découlent naturellement de la notion de défaut. Nous caractérisons notamment les mots de complexité palindromique minimale sur un alphabet à deux lettres et nous démontrons que les mots infinis obtenus par codage de rotations sur deux intervalles atteignent la complexité palindromique maximale. Dans une troisième partie, nous proposons une méthode basée sur des algorithmes de fractions continues multidimensionnelles pour la génération de droite discrètes 3D 6-connexes. Les expérimentations illustrent que la complexité en facteurs des mots ainsi générés serait linéaire. Cela se compare avantageusement aux autres définitions de droites discrètes 3D 6-connexes dont la complexité en facteurs est quadratique. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : combinatoire des mots, géométrie discrète, pavage, polyomino, complexité palindromique, droite discrète, algorithme de fractions continues multidimensionnelles.

Type:	Thèse ou essai doctoral accepté
Informations complémentaires:	La thèse a été numérisée telle que transmise par l'auteur
Directeur de thèse:	Brlek, Srecko
Mots-clés ou Sujets:	Combinatoire des mots, Géométrie discrète, Pavage, Polyomino, Complexité palindromique, Droite discrète
Unité d'appartenance:	Faculté des sciences > Département de mathématiques
Déposé par:	Service des bibliothèques
Date de dépôt:	24 oct. 2012 18:04
Dernière modification:	01 nov. 2014 02:23
Adresse URL :	http://archipel.uqam.ca/id/eprint/4940

Modifier les métadonnées (propriétaire du document)

Statistiques