Mathematical Games Hosted by Ed Pegg Jr. [Episode 16: Space-Filling Curves]

This is Ed Pegg Jr. And I'll be talking about space filling curves today. And I'm waiting for a little bit of time for people to come in and we'll soon be starting this, this little talk about space filling curves. So this is my mathematical game series. The writer Martin Gardner had a column in Scientific American called mathematical games for 25 years and left a series of 15 books where he expanded on the items that were in the columns he continued to write. But much of recreational math is still based on the things that Martin Gardner talked about. However, with the advances in computers, there's many more things that have been found about many of these items. So I'll be talking about some of the new things that have been found since Martin Gardner wrote about space filling curves, in particular the dragon curve in, in his column for Scientific American. So we can start with our demonstrations project. Demonstrations.wolfram.com we have many different items that have space filling curves within them and these are all free to download. I'll be using some of these items in the course of this talk. And there are also many different ways of expressing the dragon curve, which is one of the most famous space filling curves. So I'll be using some of those as well. So what is a space filling curve? So one way of looking at it is here's a way of filling up a square with three line segments. If we add on that segment in various ways to the original set of segments, we can get a larger curve. And as we iterate that process over and over again, it fills more and more. Not sure why that didn't work. It fills more and more of the original square. So that is the Hilbert curve. And there's a actual mathematical function called Hilbert curve that you can look at mathematical function. And the Moore curve is similar, but it has a different substitution. So you can show different substitutions, different layers. So here's one iteration of the Moore curve and here's one iteration of the Hilbert curve. This is a demonstration by Robert Decal. So Martin Gardner and in the book Mathematical Magic show, described this as a puzzle. You have this curve and he wondered, how can you present this curve as a, how can you generate this curve? And one method is to fold a piece of paper. If you fold it once and then unfold it. So there's a 90 degree angle. You get this particular curve. If you, if you fold it twice and three times and then unfold it to 90 degrees, you get this odd curve in your piece of paper. This is something you can try with say a Long receipt. And another way of looking at it is to fold it in half and then fold it in half again and you get this next generation of the curve and the next generation here and the next generation and so on. So this is a geometric version of a geometric method for generating this object known as the Dragon curve, which you can generate by folding a piece of paper. And this is easy to do with code. If we start here, let's go down to zero. Not sure why that's not working. All right, we can add on to the curve by following this series which is given by this code here. And we can gradually grow the curve and once we've started generating it, we can just keep on going. So here's 60, 65,000 steps of the Dragon curve. Now notice that it's making this particular shape, this big blob here, which is repeated several times in different orientations but in different sizes. And that's one feature of this particular fractal is you get these different shapes repeated. And when you keep expanding like this, you'll see that there's a related set of shapes. Also if you take copies of this, you can see that in the negative you could fit in one of these curves in where, where the, the black and the white are very similar. It turns out this, this shape will tile the plane. You just need repeated copies of it. A related object is the Wonder Lease curve. Starts like that. And when you repeat you get these variations. And there are three different types, 1, 2 and 3. So once this got started with the Hilbert curves and the Dragon curve, many other of these types were looked at to see what could be done with them. And then it was generalized by Astrid Lindenmeyer who developed L systems. And we have a L system function and the resource function Wolfram function Repository. You can take one of these curves that describes a, how a, how a curve will behave. And once you have that code, here's the Dragon curve we just looked at. The code for that is, is here. This is, this is one way of representing the code. X goes to this set, Y goes to this set where the plus and minus deal with how an object is, is can be flipped. So with, with these bits of Lindenmaier codes we can get the box fractal, the Dragon curve, the Hilbert curve, the, the snowflake Yana curve, Sia Prinsky arrowhead curve, and so on. We'll go be going into those. So this is one method for, for generating these curves. There's also what's called the Ventrelli notation, which, which is something I'LL be using. So basically the first part of the code is the direction that it goes based on these values. And there's both, both a square grid notation and a very related triangular grid notation, which basically removes the 1:1 and minus 1:1. And then there's a method for how it gets flipped. So, for example, this, this arrow here has the ending arrow on this side, but this next one, it's backwards. And the arrows arrowhead is on the other side. So the first one is one one. The next one is minus one, minus one. There's four different types of flips that are possible with a segment. And with this particular notation, you can generate a space filling curve, which is something that Dieter Siemen did with this code here. This notebook will be posted on the community site sometime after this talk. And with all of these, it turns out there's multiple ways of generating these different curves. For the Sierpinski arrowhead curve and Dr. Wolfram's new kind of science, he shows 12 different small bits of code that will generate the pattern. Usually once there's one way of generating a curve, it turns out that there's many different ways. With the Ventrilli notation, here's a piece of code for generating the dragon curve, or the harder Highway Dragon, named after the discoverers. With a slightly different code, you can get what's called the polya sweep. So in the first, here's the first step of the dragon curve. Here's the first step of the polya sweep. But the curves that they generate at say, step nine look quite different. Here's the dragon curve and here's the poly sweep. But it's hard to see what's going on with the polya sweep. So what we can do is round the corners and here we have in the rounded corners, here's step nine. The dragon curve looks a little bit different with the rounded corners. And you can kind of see what's happening with the poly sweep. Now, once the corners have been rounded, here's a larger image for the polyasweep. And we can use some code to look at various steps of how the polya sweep is growing. Like. So. You can see it gets quite intricate and the sort of. The pieces of the curve itself also turn into a fractal. So this is a rather elaborate pattern that comes out of this simple piece of code. A related item is reptiles, where you take a shape and you use it to make copies of itself. So with the, with the iterations of the dragon, those turn out to be reptiles. This is the Bounding fractal for the one of the. One of the dragons. And when you take two copies of itself and put it together, you get a larger copy of the same thing. That's one of the. One of the features of these dragon curves is that you can divide them into two or more copies and you basically get two copies of the original shape just scaled down. So these are different reptiles. The 30, 60, 90 triangle happens to be one. And we'll be seeing quite a few of these fractal shapes which can make copies of itself. Here's. Here's one of the different dragons here. So reptiles happen to be in the class of things that can be considered for space filling curves, just because it turns out that they tend to make many different copies of themselves while they're being generated. And there's a unsolved question that's related to this that I'll get it to later on. So the tur dragon is one of the shapes I showed. Here's. Here's the initial shape for the pur dragon. And as we iterate, it gets progressively more complicated. So here's step seven of the turd dragon, which is generated with. With these pieces of code. On the question of. Of curves, I'll be getting to that near the end. That's a good question that Bill Gosper drew attention to during a gathering for Gardener Talk. So with, with three copies of the turd dragon, we get a larger ter dragon as shown here. So here's how these steps look with. With roundedness. With. With each step you get more and more detail with these, and they divide into copies of themselves. Not sure whether this next step will work. Oops. Nope, didn't work. The inverted fur dragon is similar, but it is pinched in the middle. But again, it basically will make three copies of itself while it's being generated, each one having a pinch. Oops, that didn't want to work. But if we change one value of this, we get a rectangular filler instead. And again, it makes copies of itself. This larger rectangle has three smaller rectangles which are similar on the inside. Differentiable. I'll be getting to that in a bit. So the Hafter dragon also makes three copies of itself as so as so and with rounded corners, it's a little bit easier to see what's going on. As like. So now this is one shape which makes spirals of itself. It has a spiral part here, which you can see in larger iterations. So here's a whole bunch of root three curves, which basically means that the Initial distance traveled by the curve in the first iteration is the square root of 3. And as each one of these is generated, you get these different patterns. One of them happens to look like a spiral. Here's the turd dragon over here. And here's the color forms of these. In each case you've divided the, the shape into three copies of itself as, as, as shown here. So reptiles and space filling curves happen to be closely related because many of the things seen in space filling curves and reptiles are also seen in each other. We can go to Route 4, which includes the Sisara sweep, which is this one here. These are different rules for making the curves. And here's what they look like in four colors now. And in each of these you're generating four copies of the original curve, all size down one fourth the original size. And you can see that basically we have a 45, 45 degree triangle and it's divided into four copies of itself as shown here. Let's see here. Here's the piano. Sweet. It starts rather simply. And this one is slightly different from the Hilbert and Moore curves in that it will double, will basically backtrack at certain points of the, of the curve. And it gets progressively more and more complicated with these unusual shapes. This is also called the Holy Castle tiling. Here's the same thing but with, but with rounded corners so you can see a little bit more of what's going on. Of course, you could also use this as a, as a space filling curve. Not sure why this is boarding on me. And the Sierpinski arrowhead curve is another item that can be shown with this set of curves. Here we use a slightly different initial condition so we can get different curves out. And there's many different ways of generating the Sierpinski arrowhead curve and also many different ways of generating the Sierpinski pattern. For example, one thing I meant to put in here is Pascal's triangle. If you look at mod 2 of the Pascal triangle, you get this pattern. For rounding the corners. Basically instead of a straight line segment, you basically alter the initial curve so that it has a bump in it and that will add the curve in. As part of the code by Dieter Steemann, I showed earlier these different initial patterns. And here's other root four curves showing a variety of different patterns. And in each case, this one is called the Sierpinski family because it, it contains different generations of itself in being generated, but it's also dividing into, into multiple copies. Let's see here. And you can see that each One of these is also a reptile of a sort. Various different curves can be put together. So here's six copies of one of them and they generate the whole triangle when put together. After root four, we can look at root five. There's more of these. Here's the five dragon at the top, which is the most famous of these. You can see it looks very much like the turd dragon, but instead of having three copies making the larger shape in this one, five copies makes the larger shape. Each one of these is, is, is similar to the outer shape. And here's the pinched five dragon. This one is based on a, a DX Pentomino. You can turn that into a fractal curve. And there's, there's two different ways of representing that. And here's a, another odd shape made with five copies of itself. So these are all different sorts of fractals which are generated with space filling curves. And yes, we could, we could model these with splines by changing the initial condition. We can, we could change what these look like. We could just try that here somewhere here I've got one of the other initial conditions. So we can take this initial condition here. And let's see what happens here. Not sure why that's not letting me paste right now. There we go. I'm going to take this same thing here. As the initial conditions change, the shapes change and I'm not sure what this will do, but we can try it out. So I've changed the initial condition here and the result of that is if this comes back, Hopefully it's not too slow here. Now for this, for the slideshow environment, I don't see whether something is actually running or not. Oh, we can come back to that and see whether it's finished. So here's Mandelbrot's quartet, something he showed in his book. This is the rule for it here and you can look at different levels of it, but there we go. Let's see. So this is different levels of the Mandelbrot Quartet from Mandelbrot fractal book. So I think this one is probably done back here. Yes, here's, here's the original here you can see that with the different initial condition, the curves are slightly different, they're more rounded. And the code that's with this notebook, which I'll be posting to Community, has all the code in it and you can play around with it once I've got it posted. Changing the initial conditions will, will change the shape of the curve. Here's another famous curve by Bill Gosper. It's called the Gospel curve. And here's five different stages in the iteration. He basically starts with the set of curves in a set of seven hexagons and that allows it to grow in a shape that vaguely looks like seven hexagons put together. You get this elaborate curve here. And there's various other root seven curves. And they look like these, each one with seven copies of itself in the, in the larger form. And you can see these curves start looking a little bit wilder. These are the, these are the two variants of the Gospel curve here. These are different types of her dragons on the top here and so on. So they steadily get more and more elaborate. Here's one of the root eight curves. And a root nine curve, a piano curve. You can see that it's, it's. If you look at one of the smaller shapes, it's made from nine copies of the, of the larger shape. You can see that this here looks very much like the full curve here. Let's see, angle path is one is another way of generating these different curves. So the, the Coke one curve. Let's go to many steps here. Here's a variation of the, of the, of the Koch curve. The second Koch curve, the piano curve and angle path and Koch curves is a, is a Wolfram demonstration, Hilbert curve, Sierpinski and so on. These are all, All different usages of the substitution system fed into angle path. This is a piece of code I did a few years back. Here's another Route 9 curve here which looks rather interesting. It starts here, I'm not sure where it ends. And another curve is called the Cesaro fractal as shown on Mathworld, but it's pretty much identical to the Knopp Osgord curve. So as we change the, as we change the angle you basically get these same shapes. I'm guessing the Cesaro is basically four copies of the not boss good. And as you change the number of iterations you basically take out more and more of these segments. And as the angle changes you get different curves like so. So this is a removal process that happens to have the same sort of effect as the space filling curves or the geometric methods. So a related item is two dimensional terrain machines or termites. And here's a termite I found. It's called the, I just call it the binary counter. And as, as we step around it, just basically if it's, if it's, if the area is marked black then go straight and if it's white turn right. And as you continue. It just basically continues up and down in a 2 by n rectangle. Counting in binary. Let's see if we can show many steps of this. So here's 8 or 6000 and 6340. And basically this is 1/4 of 6340 in binary @ some stage. And this is a very slow growing termite because basically it has to count to say to get to here you'd have to count to two to the 40 and so on. And different termites have different patterns. So this is the classic Langton's ant which eventually makes a highway. But many of these termites generate patterns. That's the piano. This is a spiral pattern that's been seen with many of these. This looks like another of the space filling curves, but it also happens to be a two dimensional terrain machine. Many of the behavior seen in space filling curves are also seen in two dimensional Turing machines. Not all of them though. It's sort of a question whether certain behavior seen in a Turing machine can be seen in a, in a L system or in a substitution system. I believe that most termites will not be replicatable with space filling curves. But for example, that one probably is. This one probably is not. This one is in fact this is a space filling curve. It has different copies of different squares that generate golden rectangles and so on. So I thought I would, I would show the similarity there between the termites and space filling curves. A Another item is angular fractals such as the Koch snowflake. Like and I believe this one allows you to adjust angles and they get wildly complicated as you adjust the angles. Now it's just kind of, kind of a cloud of chaos. But it's still a, a face space filling curve. It's just not a very particularly nice looking one. But many of these will will resemble biological patterns such as seen in leaves and ferns. Here's another way of grading the dragon curve. We basically start with a set of dominoes and then we cut and slide the dominoes. And as we continue cutting and sliding, we get the herd dragon. Another substitution system is known as Hafferman's carpet. There's various different varieties of this particular fractal that will correspond with space filling curves. But again, it's not clear when a space filling curve and a substitution system such as this will align with each other. I believe most of these are not space filling curves. So root 10. There's many different curves within this particular state. Just because you have so many varieties, we can take a look at this particular one, and we can take a look at four copies of it. And we basically get a square with additions. We can also take a look at 16 copies of it, such as this one, and we get a larger square with a more complicated set of curves within the inside. And we could continue using more and more iterations to get a more complicated curve, but they would still fit together nicely, such as what's seen here. Here is a Route 12 system, which I thought was rather nice. This is another of the Dragon family, And a Route 13 piano gospel curve. So we can convert L systems to curves such as this particular L system curve here in the Dieter Steemann curve at the top, there's a conversion program for actually taking a L system notation and converting it to the Biermann notation. And you can see that it happens to work here. So we can take these different L systems and convert them into the different notation. Here's various L L systems of different sizes. And here's a really large one. Here's the 31 gasper curve with 31 copies making a tiling. And each one of these is similar to the outside shape. So here's one, a way of dividing a particular fractal shape into 31 copies of itself. Doug McKenna is one of the earlier people to look at space filling curves. And he did a. He basically compiled all of them and then started turning them into art back in the 1980s. And he has a site, Mathematics. And here's a. He actually has an iOS app which you can get from the Apple Store. And here's one of the screenshots from that app on Hilbert Curves. I believe it's called Hilbert Herbal Hilbert Curve on the Apple site. The Chaos game for iterated function systems basically starts with a. Starts with a. A simple item. Let's see if we can get this to work. We basically have three points and we basically randomly choose which point we'll go to next. And you get this Sierpinski pattern. As you change the different odds and where the points are, you get different patterns coming out. And this is what's called the Chaos game. With certain odds and certain placements for points, you get nice patterns. But often if you change the odds sufficiently, you'll get much more complicated patterns. And these can be generated with matrices. And it turns out that with these iterated function systems, which are basically based on random randomness, you can get these patterns. Here we have a, a fractal triangle system where you have the larger triangle on the outside making copies of itself on the inside and the, the Function for this is, is. Oh, let's see if I can show it. Here. It's this one. Here we have two different functions and we're basically randomly either using minus x times a constant or X times this. And when you, when you iterate that randomly 100,000 times, you get this particular fractal shape. Well if you use the super golden ratio which is psi squared plus one equals psi to the third and you use the complex, one of the complex solutions for that, you get the complex super golden ratio. And then if you use that value here it is on the complex plane to the first power, to the second power, to the third power to the fourth power to the 0th power which is 1, this is 0 over here, this is 1 and negative that complex value squared. Here it is over here you'll get a, an original quadrilateral here which is similar to this here. And you'll get copies of the two quadrilaterals here and here. And that can be used as a substitution system which generates this shape, which is the, which I call the super golden triangle. This is the psi quad substitution system. This is something I found, but it's pretty much self generating. You just basically need the roots of the, of this function here. You could use X if you wanted to. X squared plus one equals x to the third. Just solve that, use the complex value, plug in these powers and it's solved. And this is in the research function algebraic system algebra algebraic substitution tiling. And it's the psi quad tiling. Here's a larger version of it here. So we can convert L systems to iterated function series. So I, what I just, I've just shown two iterator function series. Once we have the Ventrelli notation we can say, look at the dragon curve and here's a set of two functions. And when we evaluate these 10,000 times, we get the dragon curve as a set of randomly generated dots. So iterated function systems and space filling curves happen to be related to each other. So here's the psi quad again, here's the iterated function which generates it. And here's a fractal version of it generated with the substitution tiling. But is there a space filling curve which generates something with this shape? And that's an unsolved question. It probably isn't too hard to solve, but it's an unsolved question at this point. If you can solve that or if you can solve the similar one with the plastic constant, I'd love to hear from you because that would be interesting. Would Basically tie everything together. Let's see now I mentioned there's a question about whether these were differentiable or whether they were actually curves. Oh, that was a question that Bill Gosper and his protege Julian Ziegler Huntz looked at. And basically they said if you don't have the function, you don't have the fractal. So here is a piece of code which will generate the actual curves behind a particular space filling curve. So here's the Hilbert curve. And when you put it through this piece of code here, you can generate. Let's see. Did I close that? I guess I did. If you evaluate this, hopefully this will work. It should show a bunch of Hilbert curves. Yes. So here's the Hilbert curve generated as, as an exact function. And if we plug these in, I basically, this is basically turning the, the end result curve into a, a function from 0 to 1. So if you say you could basically take any value here. Let's see if I can paste here. I can put in say 33 over 77. And this will give the location in the complex plane where the curve will, will hit, will be when it gets to that point in the infinite length curve where infinity is scaled back to one. So at this location on the complex plane is where this curve will be when, when it's traveled that, that far to infinity. So Basically I've mapped 0 to infinity to 0 to 1 for this space filling curve. And what we're saying is that for any point you can find out, for any point on the line you can find out exactly where it is in this region. Now one thing that they found with this was that various points were visited twice or three times or more. All these black dots here, these are the points in the curve where it's reached here. It's reached three times at 1924, 7, 8 and 2324. And they believe that all points are eventually visited three times. This point here seems to be a critical point. It's visited four times. Here's a way of generating the dragon curve with this function. But it's, it's much stranger looking in, in their, in their version, I've, I've asked Bill Cutler to try to expand this, this strange function, but he hasn't had time to do that recently. But you can look at his gathering for Gardener Talk where he discusses this and I'll be posting his code online. Let's see, there's also three dimensional versions of many of these curves. I'm not sure why that one's looking strange. Yes. So here's here's the Lebeg curve in three dimensions. And the Piano curve in three dimensions. And the Sierpinski arrowhead curve in three dimensions. Let me make this smaller here. Like so. Another piece of code by Robert Dickell. You can see that it's. It's much stranger looking in three dimensions. Like so. And here's an interpolated version of the Hilbert curve with spline. Somebody asked about splines earlier and here's what that starts looking like. So let me expand these some. So I've shown various ways of how iterated function systems reptiles space filling curves are and substitution systems are. Are connected. Is it possible to go from an iterated function system to a curve? Obviously you won't always be able to do that but I'm thinking sometimes you can and it would be. It would be clear if there is if it was solved when it's possible to do that. What are fractal curves for iterated function systems such as the one shown for the plastic constant or the super golden ratio. I'd be very interested in seeing those and the Hunt's Gosper way of turning a curve into an exact function be fully expanded. It would be interesting to see how much could be done with that. And also what are some other 3D space filling curves? I. Bill Gosper has been working on a 3D version of the Gosper curve but I wasn't able to get his code to work. So that's, that's something I would like to get a better version of. So that's what I had prepared and I'll be glad to take any questions that people have. If anybody has any questions feel free to post them and I'm looking through items here. I'm not sure whether Bill Gosper's function is differentiable. That's. That's something I would, I would need to try. I don't think it is just because it. It has so many different places where it can suddenly curve but that would be an interesting thing to check. And any other questions I can go back to any particular slides if anybody would like to to see any of these again. And I'll be posting this talk online sometime within the next few days at the community site. Well, if there's no questions, well I can end it here. Many thanks for attending my talk and come back next month and I'll have another topic for discussion.