Algorithms for translational tiling

Abstract

Abstract In this paper, we study algorithms for tiling problems. We show that the conditions (T1) and (T2) of Coven and Meyerowitz [E. Coven and A. Meyerowitz, Tiling the integers with translates of one finite set, J. Algebra 212(1) (1999), pp. 161–174], 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 ℤ N . In particular, we carry out a full classification of all non-periodic tilings of ℤ144. Keywords: translational tilesalgorithms 2000 Mathematics Subject Classifications : 05B4543A2568W3068T20 Acknowledgements M.N. Kolountzakis was supported by research grant No. 2569 from the University of Crete. M. Matolcsi was supported by ERC-AdG 228005, and Hungarian National Foundation for Scientific Research (OTKA), Grant Nos PF-64061, T-049301.

Locations

• Journal of Mathematics and Music - View
• arXiv (Cornell University) - View - PDF