2026-08-15T16:20:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23191 2025-10-02T12:42:29Z ddc:004 open_access

Tiling with Three Polygons Is Undecidable Demaine, Erik D. Langerman, Stefan plane tilings polygons undecidability co-RE 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Erik D. Demaine and Stefan Langerman 2025 Is Part Of LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2025.39 urn:nbn:de:0030-drops-231913 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.39 eng https://creativecommons.org/licenses/by/4.0/legalcode