HackerPapers

arXiv:2409.11582cs.CG

Tiling with Three Polygons is Undecidable

Erik D. Demaine, Stefan Langerman

HN submission. Found in a submission link or body. Submitters do not count as commenters in the main ranking; a submission is not an endorsement.

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.

arXiv comments
17 pages, 5 figures
Journal reference
DOI
Subjects
cs.CGComputational Geometry math.MGMetric Geometry

On Hacker News

No comments linking this paper were found in the collected sources. Found in 1 HN submission from Nov 2024 to Nov 2024. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments0 threads

No comments linking this paper were found in the collected sources. Open submission discussions.

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.