Small An optimal algorithm to generate tilings.
Résumé
A lot of progress has been made in tiling theory in the last ten years after Thurston (\cite{Thu90}), building on previous work by Conway and Lagarias (\cite{CL90}), introduced height functions as a tool to encode and study tilings. This allowed the authors of this paper, in previous work (\cite{Rem99}, \cite{Des01}), to prove that the set of lozenge (or domino) tilings of a hole-free, general-shape domain in the plane can be endowed with a distributive lattice structure. In this paper, we see that this structure allows us in turn to construct an algorithm that is optimal with respect to both space and execution time to generate all the tilings of a domain~$D$. We first recall some results about tilings and then we describe the algorithm.
De gros progrès on été obtenus ces dix dernières années après que Thurston ([Thu90]), à partir du travail précédent de Conway et Lagarias ([CL90]) eut introduit les fonctions de hauteur comme outil pour coder et étudier les pavages.Ces travaux ont permis, aux auteurs de ce papier, de prouver dans des articles précédents ([R ́em99], [Des01]) que l’ensemble des pavages par losanges (ou dominos) d’un domaine quelconque sans trou du plan peut-être muni d’une structure de treillis distributif.Dans cet article, nous montrons que cette structure nous permet de construire un algorithme optimal en termes d’espace et de temps d’ exécution qui engendre tous les pavages d’un domaine sans trou.Nous rappelons d’abord quelques résultats sur les pavages, puis nous décrivons l’algorithme.
Domaines
Informatique [cs]| Origine | Fichiers produits par l'(les) auteur(s) |
|---|
Loading...