from Hacker News

Tiling with Three Polygons Is Undecidable

by denvaar on 11/17/24, 5:51 AM with 27 comments

• by xianshou on 11/20/24, 12:56 AM

  First you ask how the hell someone could come up with this construction.

  Then you realize it was this guy: https://en.wikipedia.org/wiki/Erik_Demaine

• by YoumuChan on 11/20/24, 1:44 AM

  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.

• by whatshisface on 11/20/24, 2:21 AM

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

• by joebergeron on 11/20/24, 4:38 AM

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

• by bryan0 on 11/20/24, 5:58 PM

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

• by romwell on 11/20/24, 1:36 AM

  Erik Demaine always has some fun stuff for us.