Tiling with Three Polygons Is Undecidable

#1

Post by denvaar » Sun, Nov 17, 2024, 5:51 AM UTC

Tiling with Three Polygons Is Undecidable
arxiv.org

Re: Tiling with Three Polygons Is Undecidable

#2

Post by xianshou » Wed, Nov 20, 2024, 12:56 AM UTC

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

Re: Tiling with Three Polygons Is Undecidable

#3

Post by [deleted] » Wed, Nov 20, 2024, 1:30 AM UTC

xianshou wrote: post #2

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

[deleted]

Re: Tiling with Three Polygons Is Undecidable

#4

Post by romwell » Wed, Nov 20, 2024, 1:36 AM UTC

Erik Demaine always has some fun stuff for us.

Re: Tiling with Three Polygons Is Undecidable

#5

Post by YoumuChan » Wed, Nov 20, 2024, 1:44 AM UTC

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.

Re: Tiling with Three Polygons Is Undecidable

#6

Post by whatshisface » Wed, Nov 20, 2024, 2:21 AM UTC

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

Re: Tiling with Three Polygons Is Undecidable

#7

Post by heavensteeth » Wed, Nov 20, 2024, 2:35 AM UTC

xianshou wrote: post #2

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

>former child prodigy

I understand the idea behind that phrasing but I'm not sure I agree with it. Are you no longer a child prodigy once you turn 18? I don't think I'd ever say "former intelligent child".. Would I?

Re: Tiling with Three Polygons Is Undecidable

#8

Post by chuckadams » Wed, Nov 20, 2024, 2:38 AM UTC

heavensteeth wrote: post #7

xianshou wrote: post #2

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

>former child prodigy I understand the idea behind that phrasing but I'm not sure I agree with it. Are you no longer a child prodigy once you turn 18? I don't think I'd ever say "former intelligent child".. Would I?

It's a little weird to call a 43-year-old a "child prodigy", yes. The phrase is left-associative.

Re: Tiling with Three Polygons Is Undecidable

#9

Post by infogulch » Wed, Nov 20, 2024, 2:41 AM UTC

heavensteeth wrote: post #7

xianshou wrote: post #2

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

>former child prodigy I understand the idea behind that phrasing but I'm not sure I agree with it. Are you no longer a child prodigy once you turn 18? I don't think I'd ever say "former intelligent child".. Would I?

Well he was a child prodigy, but he is no longer a child. A suitable replacement would need to reword the sentence to be about the same length and include that detail without the odd sounding wording.

Re: Tiling with Three Polygons Is Undecidable

#10

Post by noman-land » Wed, Nov 20, 2024, 3:27 AM UTC

heavensteeth wrote: post #7

xianshou wrote: post #2

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

>former child prodigy I understand the idea behind that phrasing but I'm not sure I agree with it. Are you no longer a child prodigy once you turn 18? I don't think I'd ever say "former intelligent child".. Would I?

This is why I refer to my wife as my ex-girlfriend.