Rectangular tileability and complementary tileability are undecidable

Jed Yang

Research output: Contribution to journalArticle

2 Scopus citations

Abstract

Does a given set of polyominoes tile some rectangle? We show that this problem is undecidable. In a different direction, we also consider tiling a cofinite subset of the plane. The tileability is undecidable for many variants of this problem. However, we present an algorithm for testing whether the complement of a finite region is tileable by a set of rectangles.

Original languageEnglish (US)
Pages (from-to)20-34
Number of pages15
JournalEuropean Journal of Combinatorics
Volume41
DOIs
StatePublished - Oct 2014

Fingerprint Dive into the research topics of 'Rectangular tileability and complementary tileability are undecidable'. Together they form a unique fingerprint.

  • Cite this