Tiling with Three Polygons is Undecidable
2024/09/17 by Erik D. Demaine, Stefan Langerman, Demaine, Erik D. +1 · 8 voices · 3 citations
#cs.CG #math.MG
paper · pdf · doi:10.48550/arxiv.2409.11582
Abstract
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.
Cited by
Discussions
- Tiling with Three Polygons Is Undecidable [hn, 136 points, 27 comments]
- Tiling with Three Polygons is Undecidable [lobsters, 5 points, 0 comments]
- Tiling with Three Polygons is Undecidable [lemmy, 1 points, 0 comments]
- Tiling with Three Polygons Is Undecidable (arxiv.org) Main Link | Discussion [bsky, 0 points, 0 comments]
- which gender are you? i'm the staple (extract from the paper arxiv.org/pdf/2409.11582) [bsky, 0 points, 1 comments]
- Some recent progress in tiling theory, which I missed at the time. https://arxiv.org/abs/2409.11582 [bsky, 0 points, 1 comments]
- Tiling with Three Polygons Is Undecidable | arxiv.org/abs/2409.11582 [bsky, 0 points, 0 comments]
- Tiling with Three Polygons Is Undecidable https://arxiv.org/abs/2409.11582 https://news.ycombinator.com/item?id=42162271 [bsky, 0 points, 0 comments]
Related