2025/06/13 by Jack Stade, Stade, Jack · 1 citation
Computer Science · Engineering · Mathematics · #Cellular Automata and Applications #Combinatorics (math.CO) #Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics #Mathematics and Applications #Metric Geometry (math.MG) #Structural Analysis and Optimization
paper · pdf · doi:10.48550/arxiv.2506.11628
openalex publication_date 2025/06/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We show that the following problem is undecidable: given two polygonal prototiles, determine whether the plane can be tiled with rotated and translated copies of them. This improves a result of Demaine and Langerman [SoCG 2025], who showed undecidability for three tiles. Along the way, we show that tiling with one prototile is undecidable if there can be edge-to-edge matching rules. This is the first result to show undecidability for monotiling with only local matching constraints.