Tiling with Three Polygons Is Undecidable

136 pointsposted a year ago
by denvaar

7 Comments

YoumuChan

a year ago

The author gave a talk on this at Tufts during the FWCG last week. Fascinating talk.

One interesting question from audience was whether the ratio between the largest polygon piece and the smallest piece can be made bounded, as the current construction has unbounded ratio.

whatshisface

a year ago

That's reminicient of the post correspondence problem. Is the PCP still undecidable for sets of three strings?

joebergeron

a year ago

I read the title of this paper and thought to myself, “What are the chances this could be Erik Demaine?”. And sure enough!

bryan0

a year ago

While not proven, is the intuition that this will also be undecideable for 1 and 2 polygon tilings?

romwell

a year ago

Erik Demaine always has some fun stuff for us.