Tiling with Three Polygons is Undecidable

• Published in 2024
• Added on 2024-12-02

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.

Links

• http://arxiv.org/abs/2409.11582v1
• http://arxiv.org/pdf/2409.11582v1

Other information

BibTeX entry

@article{TilingwithThreePolygonsisUndecidable,
	key = {TilingwithThreePolygonsisUndecidable},
	type = {article},
	title = {Tiling with Three Polygons is Undecidable},
	author = {Erik D. Demaine and Stefan Langerman},
	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.},
	comment = {},
	date_added = {2024-12-02},
	date_published = {2024-12-07},
	urls = {http://arxiv.org/abs/2409.11582v1,http://arxiv.org/pdf/2409.11582v1},
	collections = {basically-computer-science,easily-explained,fun-maths-facts,geometry},
	url = {http://arxiv.org/abs/2409.11582v1 http://arxiv.org/pdf/2409.11582v1},
	year = 2024,
	urldate = {2024-12-02},
	archivePrefix = {arXiv},
	eprint = {2409.11582},
	primaryClass = {cs.CG}
}