Pavages et Bases de Grobner

Abstract : 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.
Document type :
Reports
Complete list of metadatas

https://hal-lara.archives-ouvertes.fr/hal-02101831
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:07:30 AM
Last modification on : Wednesday, November 20, 2019 - 2:50:27 AM

File

RR2001-51.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02101831, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

7

Files downloads

8