Paper by Erik D. Demaine
- 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”, in Abstracts from the 23rd Thailand-Japan Conference on Discrete and Computational Geometry, Graphs, and Games (TJCDCGGG 2021), September 3–5, 2021, pages 28–29.
A family of 2-dimensional shapes 𝒯 is a called a tiling if they
(rotating and reflecting are allowed) cover the whole plane without gaps or
overlaps, and if all shapes belonging to 𝒯 are congruent each other, then
the shape is called a tile. We study k-fold tilings which are
extended to cover the plane with the thickness of k folds and k-fold
tiles which belong to it. Intuitively it means that a family of
2-dimensional shapes covers the plane such that they overlap k times at
any point in the plane. Since clearly a (1-fold) tile is a k-fold tile
for any positive integer k, the subjects of our research are
2-dimensional shapes with property “not a tile, but a
k(≥ 2)-fold tile.” We call a plane shape satisfying this
property a nontrivial k-fold tile. In this talk, we clarify some facts
as follows: first, we show that for any integer k ≥ 2,
there exists a polyomino satisfying a property “not a 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 with an area of k that is a nontrivial
- Described in a blog post by David Eppstein.
- The abstract is available in PDF (154k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- MultiTiling_TJM (Multifold tiles of polyominoes and convex lattice polygons)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated June 1, 2023 by