Pavages et Bases de Grobner
Résumé
In this paper, we answer to a question of Grunbaum by proving that, for all set F of polyominoes (union of unit squares of a square lattice), we can find a Z-tiling (signed tile) of polyominoes by copies of elements of F in polynomial time. We use for this the theory of generalised Grobner bases. For instance, we can algorithmicaly find again and extend results of Lagarias and Romero on the topic.
Nous montrons que, pour toute famille F de polyomino (union fini de cases de grille), le problème du Z-pavage (pavage signé) des polycubes par des copies d'éléments de F peut être résolu en temps polynomial par l'usage de la théorie des bases de Grobner. Ceci répond à un problème posé par Grunbaum. De plus, nous pouvons ainsi retrouver et étendre de manière algorithmique les résultats obtenus par Clarias et Romerio dans ce domaine
Domaines
Informatique [cs]
Origine : Fichiers produits par l'(les) auteur(s)