Abstract
Given a polyomino, we prove that we can decide whether translated copies of the polyomino can tile the plane. Copies that are rotated, for example, are not allowed in the tilings we consider. If such a tiling exists the polyomino is called anexact polyomino. Further, every such tiling of the plane by translated copies of the polyomino is half-periodic. Moreover, all the possible surroundings of an exact polyomino are described in a simple way.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
S. W. Golomb,Polyominoes, Allen and Unwin, London (1966).
B. Grünbaum and G. C. Shephard,Tilings and Patterns, Freeman, New York (1986).
R. Penrose, Pentaplexity,Eureka 39 (1978).
R. M. Robinson, Undecidability and nonperiodicity of tilings of the plane,Invent. Math. 12, 177–909 (1971).
H. D. Shapiro, Theoretical limitations on the efficient use of parallel memories,IEEE Trans. Comput. (1978).
H. Wang, Games, logic and computers,Scientific American (1965).
H. A. G. Wijshoff and J. Van Leeuven, Arbitrary versus periodic storage schemes and tessellations of the plane using one type of polyomino,Inform. Control 62, 1–25 (1984).
Author information
Authors and Affiliations
Additional information
Communicated by Franco P. Preparata
Rights and permissions
About this article
Cite this article
Beauquier, D., Nivat, M. On translating one polyomino to tile the plane. Discrete Comput Geom 6, 575–592 (1991). https://doi.org/10.1007/BF02574705
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF02574705