Paper by Erik D. Demaine

Reference:

Kota Chida, Erik Demaine, Martin Demaine, David Eppstein, Adam Hesterberg, Takashi Horiyama, John Iacono, Hiro Ito, Stefan Langerman, Ryuhei Uehara, and Yushi Uno, “Multifold tiles of polyominoes and convex lattice polygons”, Thai Journal of Mathematics, to appear.

Abstract:

A planar shape S is a k-fold tile if there is an indexed family 𝒯 of planar shapes congruent to S that is a k-fold tiling: any point in ℝ² that is not on the boundary of any shape in 𝒯 is covered by exactly k shapes in 𝒯. Since a 1-fold tile is clearly a k-fold tile for any positive integer k, the subjects of our research are nontrivial k-fold tiles, that is, plane shapes with property “not a 1-fold tile, but a k(≥ 2)-fold tile.” In this paper, we prove some interesting properties about nontrivial k-fold tiles. First, we show that, for any integer k ≥ 2, there exists a polyomino with property “not an h-fold tile for any positive integer h < k, but a k-fold tile.” We also find, for any integer k ≥ 2, polyominoes with the minimum number of cells among ones that are nontrivial k-fold tiles. Next, we prove that, for any integer k = 5 or k ≥ 7, there exists a convex unit-lattice polygon that is a nontrivial k-fold tile whose area is k, and for k = 2 and k = 3, no such convex unit-lattice polygon exists.

Comments:

Described in a blog post by David Eppstein.

Availability:

The paper is available in PDF (1106k).

See information on file formats.

[Google Scholar search]

Related papers:

MultiTiling_TJCDCGGG2021 (Multifold tiles of polyominoes and convex lattice polygons)