Abstract FR:

Nous etudions des problemes de pavage de regions finies (appelees polycellules) de reseau regulier par des copies translatees de polycellules donnees (les paveurs). En particulier, en associant a une famille finie de paveurs une z-base (une generalisation des bases de grbner), nous caracterisons algebriquement les polycellules z-pavables par des paveurs donnes et donnons un algorithme rapide de reconnaissance (de type division). Nous donnons un algorithme qui decide en temps lineaire en le nombre de cases si un polyomino plein (homeomorphe a un disque) est pavable par des rectangles 1 q,q 1 ou q appartient a q, puis une amelioration pour la reconnaissance des polyominos manhattan (unions de rectangles poses sur une meme droite) pavables par des barres 1 p,q 1 avec p et q dans n. Pour toute famille f de polyominos, nous affirmons qu'il existe une famille finie r de rectangles telle que les rectangles pavables par f sont exactement ceux pavables par r. Nous prouvons qu'un polycube pyramidal (un empilement de briques de plus en plus petites) est pavable par dominos si et seulement si p est equilibre. En annexe, nous donnons quelques resultats isoles sur les pavages, ainsi que la construction d'un arbre ayant moins de n 1. 9 8 sommets contractible en n'importe quel arbre a n sommets.