Tiling with Three Polygons is Undecidable
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913505715683328 |
|---|---|
| author | Demaine, Erik D. Langerman, Stefan |
| author_facet | Demaine, Erik D. Langerman, Stefan |
| contents | We prove that the following problem is co-RE-complete and thus undecidable: given three simple polygons, is there a tiling of the plane where every tile is an isometry of one of the three polygons (either allowing or forbidding reflections)? This result improves on the best previous construction which requires five polygons. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_11582 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Tiling with Three Polygons is Undecidable Demaine, Erik D. Langerman, Stefan Computational Geometry Metric Geometry We prove that the following problem is co-RE-complete and thus undecidable: given three simple polygons, is there a tiling of the plane where every tile is an isometry of one of the three polygons (either allowing or forbidding reflections)? This result improves on the best previous construction which requires five polygons. |
| title | Tiling with Three Polygons is Undecidable |
| topic | Computational Geometry Metric Geometry |
| url | https://arxiv.org/abs/2409.11582 |