Two algorithms for randomly generating aperiodic tilings

https://www.chiark.greenend.org.uk/~sgtatham/quasiblog/aperiodic-tilings/

by fanf2 • 3 years ago

195 42 3 years ago

chiark.greenend.org.uk

billfruit• 3 years ago

How exactly was the 'hat' pattern arrived at? Was it through experiment or through an analytic process.

necubi• 3 years ago

There's a great story here: https://www.quantamagazine.org/hobbyist-finds-maths-elusive-....

It was found by a hobbyist playing with PolyForm Puzzle Solver

fanf23• 3 years ago

This article has some of the story behind the paper https://www.theguardian.com/science/2023/apr/03/new-einstein...

Short answer to your question: David Smith discovered the hat shape by experimentation.

mcphage2• 3 years ago

There’s another method, at least for the Penrose rhombus tilings: https://archive.bridgesmathart.org/2022/bridges2022-285.html...

The author of this was one of the authors of the Hat tile paper.

pmarreck5• 3 years ago

I think I am obsessed with aperiodic Penrose tilings. My 21 month old son's room has an area rug with such a tiling. I want to tile a bathroom in my house with them at some point. If you want to make my day, link a photo you have of one of these IRL.

It is such a wicked combination of beauty and math, like fractals.

masfuerte• 3 years ago

Photos of a Penrose pavement here https://www.maths.ox.ac.uk/outreach/oxford-mathematics-alpha... and here https://hardscape.co.uk/inspire/case-studies/maths-institute...

pmarreck5• 3 years ago

https://media.giphy.com/media/14vFOciTnQjnl6/giphy.gif

cwmma• 3 years ago

A company tried to put it on toilet paper but Roger Penrose claimed ownership so they had to stop http://bit-player.org/2017/sir-roger-penroses-toilet-paper

pmarreck5• 3 years ago

Does he have ownership over ALL aperiodic tilings or just the ones he's come up with?

Anyway, that's unfortunate. Can't he just get a cut or something?

Also, this all really begs the question as to whether this is an "invention" or just "math". Imagine if Newton's heirs had to get a cut every time Newtonian physics was used (or calculus for that matter... splitting it with Leibniz's heirs)

layer8• 3 years ago

Since it’s aperiodic, shouldn’t he only be able to claim copyright on the configurations he actually produced? Algorithms aren’t copyrightable, only concrete works fixed in a medium of expression.

madcaptenor2• 3 years ago

Where can I get such a rug? I fixed up my home office a couple years ago and it's nice except I need a rug both to make it look nice and to absorb some sound.

pmarreck5• 3 years ago

I was wrong. I found something that resembled such a tiling, but was not, in fact, such a tiling. It was a fallback position. :/

If you do find any such thing, please let me know!

tiedieconderoga• 3 years ago

Depending on how much free time you have, you may or may not want to dive into the rabbithole of aperiodic tilings in medieval Islamic architecture.

https://www.sciencenews.org/article/ancient-islamic-penrose-...

pmarreck5• 3 years ago

This is amazing. I just wish Islam was known for this still, instead of some other things.

flangola73• 3 years ago

I don't understand what's so magical about the hat. It's a non-square shape that repeats.

brickers2• 3 years ago

it’s a non-square shape that does not and cannot repeat

klyrs• 3 years ago

Technically the shape itself repeats like a mug, infinitely tiling the plane. However, that tiling is not overly repetitive -- if it's like the Penrose tiling, it can be self-similar in a handful of rotations about a single origin, but unlike a square tiling, does not admit infinitely many self-similarities.

flangola73• 3 years ago

How can you cover infinite surface without infinite number of objects?

uoaei• 3 years ago

"Aperiodic" is the opposite of "periodic"

mcphage2• 3 years ago

When people talk about patterns that repeat, they usually mean one of the 17 wallpaper groups (https://en.wikipedia.org/wiki/Wallpaper_group). And people are interested in patterns that do tile the grid completely, but don't match one of those patterns. Originally it took thousands, but people had gotten it down to 2 shapes that together tiled the grid completely, but not in one of those 17 groups.

Now, people have gotten it down to a single shape that—by itself—tiles the pattern infinitely, but not in one of those 17 groups.

motohagiography• 3 years ago

Naively, and with general interest public forum curiousity, these tiling problems seem to be about iterating the proportions of the sides of the tiles to get symmetrical shapes, but given each tile is also necessarily a hamiltonian circuit between the angles/nodes of a shape and the tiles are aperiodic, the implied visual symmetry of the shapes doesn't seem meaningful.

It seems like there would be infinite possible aperiodic tiles (with real valued side lengths), so long as the number of angles (or nodes/vertices) for a whole tile (like a triangle) has the same evenness or oddness as the number of vertices extending from the node as the number of sides of the shape it is a part of.

So to completely tile a plane aperiodically, each node/angle of a triangle must have an odd number of "sides" from its adjacent tiles stemming from it to completely tile a plane, where each angle of a hexagon must be a node with an even number of sides connecting at its vertices. Once you are more than one "hop" away from another tile, you can have even or odd numbers of verticies.

The perimeter of any plane with a complete aperiodic tiling must still be a hamiltonian path around its edge, therefore the graph of the verticies representing the angles the aperiodic tiles must also reduce to being made of other "shapes" with hamiltonian paths. It implies to me that for every tile that is odd-sided, it requires a complementary odd-sided shape somewhere in the tiling to form a hamilonian path of "hops."

It's not a sufficient condition, but naively it looks like a necessary one. No math will get done here, but from a general interest reasoning perspective, I'd wonder if tiles and hamiltonian cycles are the same thing.

fanf23• 3 years ago

The hat is part of an infinite family of aperiodic tiles, as illustrated in the last image on this page: https://cs.uwaterloo.ca/~csk/hat/

This adjustability was a surprise, we have not seen an aperiodic tiling like this before.

wwarner2• 3 years ago

I feel like any discussion of aperiodic tiling that doesn’t mention de Bruijn is missing the mark. He showed that aperiodicity results from projecting wireframes in 4 or more dimensions onto a plane. The non-repetitive patterns appear for the same reason that irrational numbers appear in Euclidian geometry.

powerset• 3 years ago

When I tried to give a quick explanation of what an aperiodic was to a friend recently, calling it a geometric version of irrational numbers was the easiest way to do it. Glad to hear my explanation had some substance to it, and wasn't just one of those "you can think of it like this, but that's not what it really is" explanations.

fanf23• 3 years ago

Isn’t de Bruijn’s method specific to Penrose tiles? The aperiodic monotile paper says in section 2 that it is an open question whether the cut-and-project method can construct hat tilings. So de Bruijn would have been no help to solve Simon Tatham’s problem of how to generate hat tile puzzle grids. His two algorithms are the old one his Loopy puzzle uses for Penrose grids, and the new one it uses for hat grids.

You can play Loopy on a hat tile grid here: https://www.chiark.greenend.org.uk/~sgtatham/puzzles/js/loop...

wwarner2• 3 years ago

yes, agree, but you’re proving my point because as you say the interesting thing about the hats is that they don’t fit into the simple geometric explanation of other aperiodic tilings.

scythe• 3 years ago

I'd be surprised if the pinwheel tilings — which have tiles that take on an infinite number of relative angles — could be reproduced in this manner. It seems like projecting a periodic set in high dimensions should give at most a finite number of cell orientations, although I can't prove it offhand.

woudsma• 3 years ago

Near my previous job there was a park with similar tiling [0]. I'm not sure if the pattern qualifies as truly aperiodic(?) but it triggered my brain every day, I couldn't not look at it. I love these kinds of patterns, they always invoke my curiosity. Just like in music irregularity makes things interesting. Something for your brain to solve. You know there has to be logic behind a seemingly random pattern.

[0] https://www.dutchdesignawards.nl/gallery/funenpark/

isaacg• 3 years ago

That pattern looks periodic, but it's super cool! I think the periodic unit is a flower shape consisting of 8 tiles: 2 in the middle making a hexagon, and then 6 more around the hexagon, like the petals of a flower.

csense• 3 years ago

This website is a refreshing breath of fresh air. There's no "sign up with your email newsletter," it's a traditional webhost (not a Medium or a Substack), there's almost no styling / images / branding, it doesn't churn and stutter due to the behind-the-scenes gyrations of the latest monstrous multi-megabyte JavaScript framework with hundreds of dependencies.

Simon Tatham (the author of this article) is the developer of PuTTY [1], an open source Windows native SSH client, and Simon Tatham's Portable Puzzle Collection [2], a bunch of simple games implemented in portable C (with OS-specific frontends, or you can play them in-browser via WebAssembly).

The website has been updated in ways that improve it (this just-written article is a huge amount of informative content, and being able to play a puzzle in-browser via WASM is very welcome), but it never jumped on any of the 21st century design bandwagons that have taken over most of the WWW (many of which, I suspect, only exist to create jobs for web developers and branding consultants).

[1] PuTTY https://www.chiark.greenend.org.uk/~sgtatham/putty/

[2] https://www.chiark.greenend.org.uk/~sgtatham/puzzles/

paulddraper2• 3 years ago

Agreed.

Also it could benefit from a modicum of CSS.

wizzwizz4• 3 years ago

While Firefox displays it badly, Dillo displays it quite nicely, as does my home-rolled web browser. It used to be that, if you wanted something better than black-on-white left-aligned sans-serif, you'd configure your browser to your own tastes; I wonder why it doesn't work that way any more?

8n4vidtmkvmk• 3 years ago

hard. https://i.imgur.com/ZNNU95P.png

jakkos2• 3 years ago

Bookmark

atorodius• 3 years ago

There is a „favorite“ button FYI :)

jakkos2• 3 years ago

I read hackernews most of the time on a phone app that doesn't support favoriting :(

rcrill• 3 years ago

I'm not a programmer, but I could use a piece of software (Python?) that could generate the "Einstein" tiles and give me the location/orientation of each to cover a large square (probably 65K tiles). I can take it from there to generate the graphics I need, but I'm stuck at this step.

Two algorithms for randomly generating aperiodic tilings

Related Stories