Pavages et Bases de Grobner - Archive ouverte HAL Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2001

Pavages et Bases de Grobner

(1)
1

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
Fichier principal
Vignette du fichier
RR2001-51.pdf (356.73 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-02101831 , version 1 (17-04-2019)

Identifiants

  • HAL Id : hal-02101831 , version 1

Citer

Olivier Bodini. Pavages et Bases de Grobner. [Research Report] LIP RR-2001-51, Laboratoire de l'informatique du parallélisme. 2001, 2+31p. ⟨hal-02101831⟩
11 Consultations
97 Téléchargements

Partager

Gmail Facebook Twitter LinkedIn More