Paper by Erik D. Demaine

Reference:

Erik D. Demaine and Stefan Langerman, “Tiling with Three Polygons is Undecidable”, in Abstracts from the 31st Annual Fall Workshop onComputational Geometry, November 15–16, 2024.

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:

The full paper is available as arXiv:2409.11582.

Length:

The abstract is 5 pages.

Availability:

The abstract is available in PDF (367k).

See information on file formats.

[Google Scholar search]