Dissertations / Theses on the topic 'Pavage du plan'

La première partie de cette thèse est centrée sur le problème de l'existence et de l'exhibition effective de pavages de figures finies du PLDAN, avec deux barres (l'une horizontale HM, l'autre verticale VN) avec l'idée de produire des algorithmes de pavages de complexité satisfaisante (linéaire). Nous donnons d'abord trois algorithmes de pavage par H2 et V2 : le premier très général est une conséquence directe de la théorie des couplages d'un graphe; le second permet de paver en temps linéaire toute figure horizontalement convexe. Enfin, nous indiquons un algorithme de pavage d'une figure sans trou, du A W. P. Thurston. Dans le cas général, nous donnons un algorithme de pavage des trapèzes. En introduisant la notion de col, nous donnons un algorithme de pavage des figures horizontalement convexes. Ce même algorithme se généralise à une classe de figures plus grande (figures sans pont). Dans la deuxième partie, nous reprenons les travaux de P. Rosensthiel et de A. Wu et A. Rosenfeld sur la reconnaissance de graphes sous-jacents à un réseau d'automates : nous généralisons la reconnaissance d'un rectangle aux structures classiques : tore, cylindre, moebius et sphère. Pour ce faire, nous avons introduit des méthodes (dans un espace discret) analogues à celles de la géométrie différentielle

Dans cette thèse, nous construisons des pavages de la droite réelle et du demi-plan hyperbolique à l’aide de représentants efficaces d’automorphismes IWIP du groupe libre Fn. Dans un premier temps, nous utilisons la substitution définie par P. Arnoux, V. Berthé, A. Siegel, A. Hilion associée à un représentant efficace d’un automorphisme IWIP pour générer des espaces de pavages substitutifs apériodiques de la droite réelle. Nous montrons, en nous servant d’un théorème de connexité des représentants efficaces d’automorphismes IWIP dû à J. Los, que le type topologique de ces espaces de pavages est indépendant du choix du représentant. Nous associons ainsi, à homéomorphisme près, un espace de pavages de la droite réelle à une classe d’automorphisme externe IWIP de Fn, puis à une classe de conjugaison d’un élément IWIP dans Out(Fn). D’autre part, nous construisons à partir des éléments de l’espace de pavage de la droite réelle précédemment construits des pavages faiblement apériodiques pour le groupe des transformations affines du demi-plan hyperbolique. Nous étudions les propriétés topologiques et dynamiques de ces espaces de pavages du plan hyperbolique. Enfin, dans une dernière partie, nous montrons que les espaces de pavages précédemment construits peuvent être munis d’une structure lisse en se servant de leur structure de limite projective<br>In this thesis, we construct tilings of the real line and the hyperbolic half-plane using train-track maps of IWIP free group automorphisms. One the one hand, we use a substitution defined by P. Arnoux, V. Berthé, A. Siegel, A. Hilion coming from a train-track map of a IWIP free group automorphism to generate substitutive aperiodic tilings of the real line. We show, thanks to a theorem of J. Los about connectivity of train-track representatives of an IWIP automorphism, that the topological type of those tiling spaces is the same up to a choice of train-track representative. Thus we associate, up to an homeomorphism, a tiling space of the real line to a class of an IWIP outer automorphism of Fn, then we extend this result to a conjugacy class of an IWIP element in Out(Fn). On the other hand, we construct from elements of tiling spaces of the real line previously defined, a set of weakly aperiodic for the affine group tilings of the hyperbolic half-plane. We study topological et dynamical properties of the tiling space generated by those hyperbolic tilings. Finally, in the last section we endow tiling spaces previously constructed with a smooth structure thanks to their inverse limit structure

Nous étudions dans ce mémoire les propriétés des ensembles de pavages engendrés par des jeux de tuiles de Wang exhibant une ou plusieurs directions de déterminisme local, en accordant une importance toute particulière aux jeux déterministes dans les quatre directions diagonales simultanément, dits 4-way déterministes. Après avoir proposé une construction alternative d’un jeu de tuiles apériodique 4-way déterministe, nous étudions plusieurs problèmes de décision sur ces objets et complétons en particulier le résultat d’indécidabilité du problème du pavage dans le cadre 4-way déterministe établi par Lukkarila en montrant l’indécidabilité du problème du pavage périodique 4-way déterministe. Nous montrons également que des familles complexes de coloriages du plan telles que celles engendrées par les substitutions restent sofiques dans un cadre 4-way déterministe. Nous proposons une bi-déterminisation des constructions de jeux de tuiles point-fixe de Durand, Romashchenko et Shen et en tirons quelques premières applications. Enfin, nous considérons l’opportunité d’élargir le rayon de la règle locale de déterminisme afin de limiter les directions d’expansivité et ainsi de permettre la construction localement déterministe de systèmes de particules et collisions non triviaux. Nous introduisons un nouveau modèle syntaxique commode afin de travailler à rayon deux et revisitons des problématiques de Lukkarila dans ce cadre<br>In this thesis, we study some properties of the sets of tilings generated by Wang tilesets that exhibit one or more directions of local determinism, focusing in particular on tilesets that are simultaneously deterministic in the four diagonal directions, referred to as 4-way deterministic. After having exposed an alternative construction of a 4-way deterministic aperiodic tileset, we study several decision problems on these objects and complete in particular Lukkarila’s result of undecidability of the Domino Problem in the 4-way deterministic setting proving the undecidability of the 4-way deterministic periodic Domino Problem. We also prove that some complex families of colorings of the plane such that those generated by substitutions remain sofic in the 4-way deterministic setting. We propose a bi-determinization of the constructions by Durand, Romashchenko and Shen of fixed-point tilesets and give some first applications. Finally, we investigate the idea of extending the radius of the local rule of determinism in order to reduce the set of directions of expansiveness and thus allow the local realization of non-trivial particles and collisions systems. We introduce a new and convenient syntactic model to deal with radius two and revisit some of Lukkarila’s problems in this setting

Cette thèse est une contribution à l'étude de problèmes de pavages par des dominos. Nous montrons comment élargir au cas d'un polyomino avec des trous la méthode de Thurston qui permet de paver en temps linéaire un polyomino sans trous par des dominos. Nous présentons un algorithme de pavage de complexité O(kn) pour un polyomino avec n cellules et k trous. En particulier, cet algorithme est linéaire pour un polyomino avec un nombre borné de trous. Nous exposons aussi l'état de nos recherches sur le problème du pavage de cardinalité maximale et, plus généralement, sur celui du couplage maximum dans un graphe biparti plan. Nous présentons un algorithme original de couplage dont la complexité reste encore à déterminer. Nous considérons enfin le problème de la reconstruction du pavage d'un rectangle à partir de ses projections orthogonales. Ce problème connu depuis une dizaine d'années restait non résolu. Nous présentons un algorithme polynomial qui réalise cette reconstruction.