Algorithms for translational tiling

2008/10/23 by Mihail N. Kolountzakis, Máté Matolcsi, Kolountzakis, Mihail N. +1
Computer Science · Materials Science · Physics and Astronomy · #05B45 #43A25 #68T20 #68W30 #Cellular Automata and Applications #Color Science and Applications #FOS: Mathematics #Number Theory (math.NT) #Quasicrystal Structures and Properties

paper · pdf · doi:10.48550/arxiv.0810.4338

openalex publication_date 2008/10/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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₁₄₄.

Citations

• Complex Hadamard matrices and the Spectral Set Conjecture
• The undecidability of the domino problem

Related

• Functional tilings and the Coven-Meyerowitz tiling conditions
• Combinatorial and harmonic-analytic methods for integer tilings
• The structure of translational tilings in ℤ^d
• The Coven-Meyerowitz tiling conditions for 3 odd prime factors
• An Optimal Algorithm for Tiling the Plane with a Translated Polyomino