Algorithms for translational tiling

DOI10.1080/17459730903040899MaRDI QIDQ3391792zbMATH OpenOpenAlexFDO

Authors Mihail N. Kolountzakis, Máté Matolcsi

Publication date 13 August 2009

Published in Journal of Mathematics and Music (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0810.4338

zbMATH Keywords

algorithmstranslational tiles

Mathematics Subject Classification ID

Combinatorial aspects of tessellation and tiling problems (05B45) Special sequences and polynomials (11B83) Fourier and Fourier-Stieltjes transforms on locally compact and other abelian groups (43A25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Symbolic computation and algebraic computation (68W30)

Abstract: In this paper we study algorithms for tiling problems. We show that the conditions $(T1)$ and $(T2)$ of Coven and Meyerowitz, conjectured to be necessary and sufficient for a finite set $A$ to tile the integers, can be checked in time polynomial in $diam(A)$. We also give heuristic algorithms to find all non-periodic tilings of a cyclic group $Z_N$. In particular we carry out a full classification of all non-periodic tilings of $Z_{144}$.

Recommendations

• On the tiling by translation problem
• Tiling the integers with aperiodic tiles
• Combinatorial and harmonic-analytic methods for integer tilings
• The Coven-Meyerowitz tiling conditions for 3 odd prime factors
• The structure of translational tilings in \(\mathbb{Z}^d\)

Cites work

• Arbitrary versus periodic storage schemes and tessellations of the plane using one type of polyomino
• scientific article; zbMATH DE number 2202929 (Why is no real title available?)
• scientific article; zbMATH DE number 5257131 (Why is no real title available?)
• New perspectives on rhythmic canons and the spectral conjecture
• On Fuglede's conjecture and the existence of universal spectra
• On Keller's conjecture for certain cyclic groups
• On the factorisation of finite abelian groups
• On the factorisation of finite abelian groups. II
• Spectra of certain types of polynomials and tiling of integers with translates of finite sets.
• Spectral sets and factorizations of finite abelian groups
• Tesselation of integers
• Tiling the integers with translates of one finite set
• Tiling the line with translates of one tile
• Undecidability and nonperiodicity for tilings of the plane

Cited in

(19)

• Extended Vuza canons
• A SAT encoding to compute aperiodic tiling rhythmic canons
• Tiling algebra for constraint-based layout editing
• The Coven-Meyerowitz tiling conditions for 3 odd prime factors
• Binary nontiles
• Combinatorial and harmonic-analytic methods for integer tilings
• New perspectives on rhythmic canons and the spectral conjecture
• Tiling the integers with aperiodic tiles
• Translational Prototiles on a Lattice
• scientific article; zbMATH DE number 1445361 (Why is no real title available?)
• The structure of translational tilings in \(\mathbb{Z}^d\)
• On the structure of spectral and tiling subsets of cyclic groups
• Periodicity and decidability of tilings of \(\mathbb{Z}^2\)
• Maximally even tilings
• Polychromatic colorings on the integers
• An integer linear programming model for tilings
• Orthogonal Fourier analysis on domains
• The Coven-Meyerowitz tiling conditions for three prime factors: the even case
• Computing aperiodic tiling rhythmic canons via SAT models

This page was built for publication: Algorithms for translational tiling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3391792)