Paper by Erik D. Demaine

Reference:

Erik D. Demaine and Stefan Langerman, “Tiling with Three Polygons is Undecidable”, in Proceedings of the 41st International Symposium on Computational Geometry (SoCG 2025), Kanazawa, Japan, June 23–27, 2025, 39:1–39:16.

BibTeX

@InProceedings{ThreeTiles_SoCG2025,
  AUTHOR        = {Erik D. Demaine and Stefan Langerman},
  TITLE         = {Tiling with Three Polygons is Undecidable},
  BOOKTITLE     = {Proceedings of the 41st International Symposium on Computational Geometry (SoCG 2025)},
  bookurl       = {https://socg25.github.io/socg.html},
  ADDRESS       = {Kanazawa, Japan},
  MONTH         = {June 23--27},
  YEAR          = 2025,
  PAGES         = {39:1--39:16},

  length        = {16 pages},
  doi           = {https://dx.doi.org/10.4230/LIPIcs.SoCG.2025.39},
  dblp          = {https://dblp.org/rec/conf/compgeom/DemaineL25},
  comments      = {This paper is also available as <A HREF="https://arXiv.org/abs/2409.11582">arXiv:2409.11582</A> and from <A HREF="https://doi.org/10.4230/LIPIcs.SoCG.2025.39">LIPIcs</A>.
                   <P>
                   An <A HREF="https://edemaine.github.io/three-tiles">open-source web app</A> implementing the construction is available on <A HREF="https://github.com/edemaine/three-tiles">GitHub</A>.},
  replaces      = {ThreeTiles_CGW2024},
  papers        = {ThreeTiles_CGW2024},
}

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.

Comments:

This paper is also available as arXiv:2409.11582 and from LIPIcs.

An open-source web app implementing the construction is available on GitHub.

Length:

The paper is 16 pages.

Availability:

The paper is available in PDF (730k).

See information on file formats.

[Google Scholar search]

Related papers:

ThreeTiles_CGW2024 (Tiling with Three Polygons is Undecidable)