Undecidability of Translational Tiling of the Plane with Orthogonally Convex Polyominoes
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918059458953216 |
|---|---|
| author | Yang, Chao Zhang, Zhujun |
| author_facet | Yang, Chao Zhang, Zhujun |
| contents | The first undecidability result on the tiling is the undecidability of translational tiling of the plane with Wang tiles, where there is an additional color matching requirement. Later, researchers obtained several undecidability results on translational tiling problems where the tilings are subject to the geometric shapes of the tiles only. However, all these results are proved by constructing tiles with extremely concave shapes. It is natural to ask: can we obtain undecidability results of translational tiling with convex tiles? Towards answering this question, we prove the undecidability of translational tiling of the plane with a set of 7 orthogonally convex polyominoes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_12726 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Undecidability of Translational Tiling of the Plane with Orthogonally Convex Polyominoes Yang, Chao Zhang, Zhujun Combinatorics Computational Geometry Metric Geometry The first undecidability result on the tiling is the undecidability of translational tiling of the plane with Wang tiles, where there is an additional color matching requirement. Later, researchers obtained several undecidability results on translational tiling problems where the tilings are subject to the geometric shapes of the tiles only. However, all these results are proved by constructing tiles with extremely concave shapes. It is natural to ask: can we obtain undecidability results of translational tiling with convex tiles? Towards answering this question, we prove the undecidability of translational tiling of the plane with a set of 7 orthogonally convex polyominoes. |
| title | Undecidability of Translational Tiling of the Plane with Orthogonally Convex Polyominoes |
| topic | Combinatorics Computational Geometry Metric Geometry |
| url | https://arxiv.org/abs/2506.12726 |