Rectangular tileability and complementary tileability are undecidable

Jed Yang

doi:10.1016/j.ejc.2014.03.008

Rectangular tileability and complementary tileability are undecidable

Jed Yang

School of Mathematics

Research output: Contribution to journal › Article › peer-review

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 language	English (US)
Pages (from-to)	20-34
Number of pages	15
Journal	European Journal of Combinatorics
Volume	41
DOIs	https://doi.org/10.1016/j.ejc.2014.03.008
State	Published - Oct 2014

Bibliographical note

Funding Information:
I am grateful to my advisor Igor Pak for proposing these problems, helpful conversations, reading this paper, and providing invaluable feedback. I also thank the anonymous referees for attentive reading of the paper and useful comments. The work is supported by the NSF under Grant No. DGE-0707424 .

Publisher link

10.1016/j.ejc.2014.03.008

Find It

Find It at U of M Libraries

Cite this

@article{50887f78044a48bfaf64d9e48e30dbda,

title = "Rectangular tileability and complementary tileability are undecidable",

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.",

author = "Jed Yang",

note = "Funding Information: I am grateful to my advisor Igor Pak for proposing these problems, helpful conversations, reading this paper, and providing invaluable feedback. I also thank the anonymous referees for attentive reading of the paper and useful comments. The work is supported by the NSF under Grant No. DGE-0707424 . ",

year = "2014",

month = oct,

doi = "10.1016/j.ejc.2014.03.008",

language = "English (US)",

volume = "41",

pages = "20--34",

journal = "European Journal of Combinatorics",

issn = "0195-6698",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Rectangular tileability and complementary tileability are undecidable

AU - Yang, Jed

N1 - Funding Information: I am grateful to my advisor Igor Pak for proposing these problems, helpful conversations, reading this paper, and providing invaluable feedback. I also thank the anonymous referees for attentive reading of the paper and useful comments. The work is supported by the NSF under Grant No. DGE-0707424 .

PY - 2014/10

Y1 - 2014/10

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84897935251&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84897935251&partnerID=8YFLogxK

U2 - 10.1016/j.ejc.2014.03.008

DO - 10.1016/j.ejc.2014.03.008

M3 - Article

AN - SCOPUS:84897935251

SN - 0195-6698

VL - 41

SP - 20

EP - 34

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

ER -

Rectangular tileability and complementary tileability are undecidable

Abstract

Bibliographical note

Publisher link

Find It

Other files and links

Fingerprint

Cite this