Les problèmes de satisfaction de contraintes géométriques (GCSP) sont omniprésents dans les applications de CAO, de robotique ou de biologie moléculaire. Ils consistent à chercher les positions, orientations et dimensions d'objets géométriques soumis à des relations géométriques. Le but de la thèse était de proposer une méthode complète et efficace pour la résolution de GCSP. Dans la première partie, nous comparons des méthodes de résolution et de décomposition, et optons pour la décomposition de Hoffmann et al. et la résolution par intervalles. Nous définissons un cadre général pour l'étude de la rigidité, concept central dans les techniques de décomposition géométrique. Dans la seconde partie, nous analysons la méthode de Hoffmann et al., et les limites inhérentes à toute approche géométrique structurelle. Nous proposons le concept de degré de rigidité pour surmonter certaines de ces limites. Nous introduisons une nouvelle méthode de décomposition, et sa combinaison avec les techniques de réslution par intervalles.

Une brèche est un ensemble de blocs anguleux noyés dans un ciment de nature variable. Les brèches hydrothermales sont générées par un processus de fracturation, de dissolution des fragments, ainsi que des changements de composition causés par des eaux souterraines sous pression à haute température. La nature de la majorité des processus impliqués dans la formation des brèches hydrothermales est bien comprise d'un point de vue géochimique et plusieurs modèles basés sur cette perspective existent. Par contre, il n'existe pas de modèles approchant ces processus d'un point de vue géométrique. Dans ce mémoire, nous proposons un modèle basé sur les automates cellulaires, capable de simuler les principaux processus qui interviennent dans la formation des brèches. Un automate cellulaire est un modèle discret qui consiste en une grille de cellules pouvant chacune prendre à un instant donné un nombre fini d'états. Le temps est également discret et l'état d'une cellule au temps t est fonction de l'état au temps t -1 d'un nombre fini de cellules appelé son voisinage. À chaque nouvelle unité de temps, les mêmes règles sont appliquées pour toutes les cellules de la grille, produisant une nouvelle génération de cellules dépendant entièrement de la génération précédente. Cette approche est compatible avec l'aspect discret de la dissolution des minéraux et permet l'étude de l'évolution géométrique de fragments de roche virtuelle. Plus spécifiquement, on veut mesurer la complexité morphologique des fragments par leur dimension fractale de bordure, une méthode de mesure utilisée sur des échantillons réels et permettant de valider notre modèle avec des données analogiques. Un simulateur a été conçu pour mettre en oeuvre un tel modèle. Celui-ci est codé en Java et l'interface graphique est en HTML. Des expériences sur le simulateur ont mis en évidence deux régimes de dissolution: l'un limité par la diffusion (Diffusion Limited Regime -DLR), l'autre cinétique. Le premier régime dépend de la surface exposée et on y observe l'arrondissement et le lissage progressif des fragments. Le second régime est indépendant de la surface et on observe la formation de cavités dendritiques et une augmentation progressive de la complexité morphologique. D'un point de vue géochimique, le régime DLR est dit «contrôlé par la surface» alors que le régime cinétique est dit «contrôlé par le transport». Les extensions possibles au modèle sont variées et nombreuses. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Brèche hydrothermale, Automate cellulaire, Modélisation, Dissolution, Dimension fractale.

Le thème principal de cette thèse est l'étude des métriques presque-kählériennes extrémales compatibles sur une variété symplectique compacte. Nous allons généraliser les notions d'invariant de Futaki et du champ de vecteurs extrémal sur une variété kählérienne compacte au cas presque-kählérien. Nous allons montrer la périodicité du champ de vecteurs extrémal quand la forme symplectique représente une classe cohomologique entière modulo torsion. Nous donnerons une formule explicite de la courbure scalaire hermitienne en coordonnées de Darboux. Ceci nous permettra, en dimension 4, de construire des exemples de métriques strictement presque-kählériennes qui satisfont l'égalité dans les estimations de LeBrun. Nous allons étudier la stabilité sous déformations des métriques presque-kählériennes extrémales en dimension 4. Étant donné un chemin lisse de métriques presque-kählériennes compatibles avec une forme symplectique fixe, tel que au temps zéro la métrique est kählérienne et extrémale, nous prouverons, pour un temps assez petit et sous une certaine condition, l'existence d'une famille de métriques presque-kählériennes extrémales, compatibles avec la même forme symplectique, telle que chaque structure presque-complexe induite est difféomorphe à celle induite par le chemin. En particulier, le difféomoprhisme est l'identité au temps zéro. Sur une variété torique, nous allons discuter de l'unicité et la stabilité des métriques presque-kählériennes extrémales invariantes par un tore dans l'orbite 'complexifié' par l'action du groupe des hamiltoniens. ______________________________________________________________________________

Dans cette thèse, différents problèmes de la combinatoire des mots et de géométrie discrète sont considérés. Nous étudions d'abord l'occurrence des palindromes dans les codages de rotations, une famille de mots incluant entre autres les mots sturmiens et les suites de Rote. En particulier, nous démontrons que ces mots sont pleins, c'est-à-dire qu'ils réalisent la complexité palindromique maximale. Ensuite, nous étudions une nouvelle famille de mots, appelés mots pseudostandards généralisés, qui sont générés à l'aide d'un opérateur appelé clôture pseudopalindromique itérée. Nous présentons entre autres une généralisation d'une formule décrite par Justin qui permet de générer de façon linéaire et optimale un mot pseudostandard généralisé. L'objet central, le f-palindrome ou pseudopalindrome est un indicateur des symétries présentes dans les objets géométriques. Dans les derniers chapitres, nous nous concentrons davantage sur des problèmes de nature géométrique. Plus précisément, nous donnons la solution à deux conjectures de Provençal concernant les pavages par translation, en exploitant la présence dé palindromes et de périodicité locale dans les mots de contour. À la fin de plusieurs chapitres, différents problèmes ouverts et conjectures sont brièvement présentés. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Palindrome, pseudopalindrome, clôture pseudopalindromique itérée, codages de rotations, symétries, chemins discrets, pavages.

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.

Cette thèse présente principalement des résultats sur la combinatoire des droites et segments qui apparaissent naturellement dans l'étude des problèmes de visibilité en trois dimensions. Nous exposons en premier lieu des résultats sur la taille de la silhouette d'un objet vu d'un point, c'est à dire sur la complexite de l'ensemble des droites ou segments tangents à l'objet et passant par le point. Nous présentons en particulier les premières bornes théoriques non triviales pour des polyèdres non-convexes, à savoir que, sous des hypothèses raisonnables, la complexité moyenne de la silhouette est au plus la racine carrée de la complexité du polyèdre, phénomène largement observé en infographie. Nous présentons aussi des bornes, en moyenne et dans le cas le pire, sur le nombre de droites et segments tangents à quatre objets dans une scène composée d'objets polyédriques ou sphériques. Ces bornes donnent en particulier l'espoir que la complexité des structures de données globales comme le complexe de visibilité ne soit pas nécessairement prohibitive. Les bornes sur les polytopes sont également les premières à tirer parti des propriétés structurelles des scènes composées de triangles organisés en polytopes de facon réaliste, c'est à dire non nécessairement disjoints. Ces bornes induisent enfin les premières bornes non triviales sur la complexité des ombres induites par des sources lumineuses non ponctuelles. Les résultats presentés dans cette thèse améliorent significativement l'état de l'art sur les propriétés combinatoires des structures de visibilité en trois dimensions et devraient favoriser les développements algorithmiques futurs pour ces problèmes.

La physique des très hautes énergies nécessite une description cohérente des quatre forces fondamentales. La géométrie non commutative représente un cadre mathématique prometteur qui a déjà permis d'unifier la relativité générale et le modèle standard, au niveau classique, grâce au principe de l'action spectrale. L'étude des théories quantiques de champs sur des espaces non commutatifs est une première étape vers la quantification de ce modèle. Celles-ci ne sont pas simplement obtenues en récrivant les théories commutatives sur des espaces non commutatifs. En effet, ces tentatives ont révélé un nouveau type de divergences, appelé mélange ultraviolet/infrarouge, qui rend ces modèles non renormalisables. H. Grosse et R. Wulkenhaar ont montré, sur un exemple, qu'une modification du propagateur restaure la renormalisabilité. L'étude de la généralisation de cette méthode est le cadre de cette thèse. Nous avons ainsi étudié deux modèles sur espace de Moyal qui ont permis de préciser certains aspects des théories non commutatives. En espace x, la principale difficulté technique est due aux oscillations de l'interaction. Nous avons donc généralisé les résultats de T. Filk afin d'exploiter au mieux ces oscillations. Nous avons pu ainsi distinguer deux types de mélange, renormalisable ou pas. Nous avons aussi mis en lumière la notion d'orientabilité : le modèle de Gross-Neveu non commutatif orientable est renormalisable sans modification du propagateur. L'adaptation de l'analyse multi-échelles à la base matricielle a souligné l'importance du graphe dual et représente un premier pas vers une formulation des théories de champs indépendante de l'espace sous-jacent.

Les polyominos sont souvent représentés par des mots de quatre lettres ou des mots de changements de direction décrivant leur contour. La combinatoire des mots classique y joue donc un rôle descriptif important, particulièrement dans le choix d'un représentant canonique. Les mots de Lyndon fournissent, de façon naturelle, un tel représentant. Une approche systématique pour le calcul de propriétés des polyominos, basée sur une version originale d'une discrétisation du théorème de Green classique en calcul bivarié, est élaborée. Ceci nous a naturellement amené à analyser les propriétés géométriques d'ensembles du réseau discret de rondeur maximale. Pour une taille donnée, ces ensembles minimisent le moment d'inertie par rapport à un axe passant par leur centre de gravité. Nous introduisons la notion de quasi-disque et montrons entre autres que ces ensembles minimaux sont des poIyominos fortement-convexes. Nous développons également un algorithme permettant de les engendrer systématiquement. Un autre aspect concerne des propriétés sur les contours d'ensembles discrets donnant lieu à une nouvelle démonstration d'un résultat de Daurat et Nivat sur les points dits saillants et rentrants d'un polyomino. Nous présentons également une généralisation de ce résultat aux réseaux hexagonaux et montrons que le résultat est faux pour les autres réseaux semi-réguliers. Nous poursuivons par l'introduction d'opérations de mélange spéciaux sur des mots décrivant des chemins discrets selon la suite de leurs changements de direction. Ces opérations de mélange permettent d'engendrer des courbes fractales du type courbe de dragon et d'analyser certains de leurs invariants. Finalement, une généralisation aux dimensions supérieures des algorithmes précédents basés sur le théorème de Green discret, est présentée. Plus particulièrement, nous développons une version discrète du théorème de Stokes basée sur des familles de poids sur les hypercubes de dimension k dans l'espace discret Zn, k ≤ n. Quelques applications sont également décrites. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Géométrie discrète, Combinatoire des mots, Ensembles discrets, Polyominos, Quasi-disques, Chemins polygonaux, Courbes de dragon, Théorème de Green discret, Théorème de Stokes discret, Algorithmes.

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

L'objet de ce travail est l'utilisation de certains formalismes non classiques (analyses non standard, analyses constructives) afin de proposer des bases théoriques nouvelles autour des problèmes de discrétisations d'objets continus. Ceci est fait en utilisant un modèle discret du système des nombres réels appelé droite d'Harthong-Reeb ainsi que la méthode arithmétisation associée qui est un processus de discrétisation des fonctions continues. Cette étude repose sur un cadre arithmétique non standard. Dans un premier temps, nous utilisons une version axiomatique de l'arithmétique non standard. Puis, dans le but d'améliorer le contenu constructif de notre méthode, nous utilisons une autre approche de l'arithmétique non standard découlant de la théorie des Ω-nombres de Laugwitz et Schmieden. Cette seconde approche amène à une représentation discrète et multi-résolution de fonctions continues.Finalement, nous étudions dans quelles mesures, la droite d'Harthong-Reeb satisfait les axiomes de Bridges décrivant le continu constructif.