publication . Conference object . Part of book or chapter of book . 2004

Z-Tilings of polyominoes and standard basis

Olivier Bodini; Bertrand Nouvel;
Open Access English
  • Published: 01 Jan 2004
  • Publisher: HAL CCSD
Abstract
In this paper, we prove that for every set E of polyominoes (for us, a polyomino is a finite union of unit squares of a square lattice), we have an algorithm which decides in polynomial time, for every polyomino P, whether P has or not a ℤ-tiling (signed tiling) by translated copies of elements of E. Moreover, if P is ℤ-tilable, we can build a ℤ-tiling of P. We use for this the theory of standard basis on ℤ[X1,...,Xn]. In application, we algorithmically extend results of Conway and Lagarias on ℤ-tiling problems.
Subjects
free text keywords: Polyomino, Standard basis, Discrete mathematics, Time complexity, Combinatorics, Zero divisor, Minimal polynomial (linear algebra), Discrete geometry, Lattice (order), Computational geometry, Mathematics
Related Organizations
Download fromView all 2 versions
Hyper Article en Ligne
Conference object . 2004
http://link.springer.com/conte...
Part of book or chapter of book
Provider: Crossref
Powered by OpenAIRE Open Research Graph
Any information missing or wrong?Report an Issue
publication . Conference object . Part of book or chapter of book . 2004

Z-Tilings of polyominoes and standard basis

Olivier Bodini; Bertrand Nouvel;