Get the latest tech news
Tiling with Three Polygons Is Undecidable
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.
View a PDF of the paper titled Tiling with Three Polygons is Undecidable, by Erik D. Demaine and 1 other authors View PDF 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)? From: Erik Demaine [ view email][v1] Tue, 17 Sep 2024 22:16:19 UTC (79 KB)
Or read this on Hacker News