An example of "order out of chaos"

December 3, 2012 2:09 PM

"Draw some random points on a piece of paper and join them up to make a random polygon. Find all the midpoints and connecting them up to give a new shape, and repeat. The resulting shape will get smaller and smaller, and will tend towards an ellipse!" [code to make this in Mathematica] [a version which allows you to watch the process step by step, with 10 vertices or 100]
posted by ocherdraco (65 comments total)

That's pretty cool. Why does this work?
posted by Blazecock Pileon at 2:12 PM on December 3, 2012

I think this paper ("From Random Polygon to Ellipse: An Eigenanalysis," Adam N. Elmachtoub, Charles F. van Loan) explains why.
posted by ocherdraco at 2:15 PM on December 3, 2012 [3 favorites]

Connecting the midpoints iteratively is basically a kind of smoothing. Apply smoothing enough and you end up with a smooth curve.
posted by Nomyte at 2:15 PM on December 3, 2012 [1 favorite]

What I find interesting is not so much just the smoothing, but the tendency of the ellipse to arrange itself along an axis 45 degrees off the x or y axis.
posted by ocherdraco at 2:17 PM on December 3, 2012 [6 favorites]

I think eventually it goes to a point, yeah?
posted by empath at 2:19 PM on December 3, 2012 [2 favorites]

A scaling factor is applied at each iteration.
posted by Nomyte at 2:20 PM on December 3, 2012

I got one with one line segment shorter than all the others and it's slowly looping around the figure as the figure gradually smooths out. It is pretty great.
posted by shakespeherian at 2:21 PM on December 3, 2012 [1 favorite]

Yeah, the 45 degree stuff is really cool. It's not just a tendency, it happens every time due to the eigenvalue/vector properties of the averaging matrix! Also, here's some Mathematica code that makes a prettier video (ahem): link.
posted by zeptoweasel at 2:24 PM on December 3, 2012 [1 favorite]

ocherdraco: I think this comes from the fact that the domain of the random points is a square. If you have another distribution of random points, I bet the resulting ellipse will have different average characteristics.
posted by demiurge at 2:24 PM on December 3, 2012 [1 favorite]

Ooh, cool.
posted by ocherdraco at 2:25 PM on December 3, 2012

Protip: don't start with an equilateral triangle.
posted by LionIndex at 2:27 PM on December 3, 2012 [9 favorites]

If you really want to have fun with the 10/100 vertices page, select the 100 vertices option, click go, and then select the 10 vertices option and click randomize vertices. It will keep the 100 vertices but randomize a sequence of 10 of them temporarily distorting the shape. It looks pretty neat.
posted by Green With You at 2:28 PM on December 3, 2012 [4 favorites]

That's interesting, so if you had a Gaussian distribution of points, you would get a tilted ellipse too? I wish you could change it in the demo application.
posted by demiurge at 2:29 PM on December 3, 2012

I've managed to get the 100 vertices thing to give me a decently stable figure 8 (along the 45 degree thing). It's been going maybe five minute now, no clue if it will ever resolve.
posted by shakespeherian at 2:30 PM on December 3, 2012 [3 favorites]

The 45 degree thing doesn't depend on the domain of the random points being a square. For instance, you can change line 16 of the code I linked to

pts = RandomReal[NormalDistribution[], {M, 2}];

and get the same results.
posted by zeptoweasel at 2:35 PM on December 3, 2012

Protip: don't start with an equilateral triangle.

Well, any regular polygon really, but even so, it's still "approaching" an oval in that it can't get any closer to circular.
posted by Flunkie at 2:35 PM on December 3, 2012

Green With You: "If you really want to have fun with the 10/100 vertices page"

Visit the page in chrome, press CTRL+SHIFT+C. Edit the 100 to 10000. Randomize and start again.
posted by boo_radley at 2:36 PM on December 3, 2012 [7 favorites]

If you select 100 vertices and set it going, then change it to 10 vertices and click randomise without stopping it you see it re-correct itself like someone has tugged on a particular part of it. Very interesting.
posted by mnfn at 2:41 PM on December 3, 2012

I copied it to jsfiddle and modified it to use random polar coordinates, and yes you see the same convergence to a 45 degree ellipse: http://jsfiddle.net/johnwiseman/AFuDC/

(Press the run button to see it.)
posted by jjwiseman at 2:44 PM on December 3, 2012 [3 favorites]

LionIndex: Protip: don't start with an equilateral triangle.

"Draw some random points ..."
posted by IAmBroom at 2:45 PM on December 3, 2012 [1 favorite]

Apply smoothing enough and you end up with a smooth curve.

Coupled with the well-known theorem that every smooth curve is an ellipse, that pretty much explains it.
posted by Wolfdog at 2:46 PM on December 3, 2012 [5 favorites]

Visit the page in chrome, press CTRL+SHIFT+C. Edit the 100 to 10000. Randomize and start again.

You bastard.
posted by saturday_morning at 2:49 PM on December 3, 2012 [1 favorite]

So I guess you can categorize a set of random points by what sort of ellipse they tend to-- fat one, skinny one, circle. I suppose that tells you something about the distribution of points you happened to get. Is it some simple property?
posted by nat at 2:55 PM on December 3, 2012 [1 favorite]

ocherdraco: I think this comes from the fact that the domain of the random points is a square. If you have another distribution of random points, I bet the resulting ellipse will have different average characteristics.

Nope, I played around with this last week a bit. (Sorry, I didn't save my code.)
posted by madcaptenor at 2:57 PM on December 3, 2012

The 45 degree thing makes no sense to me. The averaging process is invariant to rotation. That is, if you rotated the initial configuration by, say, 10 degrees, the subsequent polygons are also rotated by 10 degrees, so the limiting shape should be rotated by 10 degrees too! Then how can the limit have a preference for certain orientations?

Going to read the paper ocherdraco linked to now.
posted by narain at 3:04 PM on December 3, 2012 [3 favorites]

Draw some random points

Sure, but any triangle gonna stay that triangle, just smaller. I kind of wonder if all the interestingness of this comes from including re-entrant corners or crossing the lines and then having those get smoothed out. If you want to get really technical, the example on the page has one line sticking out into space, so it's not even a "polygon".
posted by LionIndex at 3:07 PM on December 3, 2012

If you start with a square, though, it will remain a square, and any regular polygon should reproduce itself indefinitely.
posted by jamjam at 3:08 PM on December 3, 2012

It will tend toward an ellipse, is all, and that tendency is contingent upon the number of points. With 3 points, the closest you'll get to an ellipse is a triangle, same as with a square. How do you make an ellipse out of four line segments? You don't, but that doesn't mean it isn't tending toward one.
posted by shakespeherian at 3:11 PM on December 3, 2012 [1 favorite]

Also wasn't this a windows 95 screensaver?
posted by boo_radley at 3:14 PM on December 3, 2012

The Elmachtoub / Van Loan article is an interesting one. I'm sort of amazed I never heard of this problem or just stumbled across it in playing around myself... it seems like a very natural question, and the result is so surprising it should really be better known. So what I'm saying is: Good Post!
posted by Wolfdog at 3:18 PM on December 3, 2012

I think that the 45 degree thing is answered in the literature concerning Principal Component Analysis (PDF).
posted by Phyllis Harmonic at 3:20 PM on December 3, 2012

Sometimes two different parts of the graph will form parts of different ellipses, and you can pick one to root for being the ellipse that eventually consumes the other. Generally you can tell which one is going to win pretty early on just by which one's larger. The losing ellipse will generally take a long time to die completely, though, fighting its bravest even in the face of certain annihilation. At the end the final corner to go will still be holding on to the shape it once believed it could be, staying strong, before being assimilated into the conforming whole of the victor. Its points will become indistinguishable from the rest in a final insult to everything it stood for, and as an example to all the others who might think of getting out of line. But there's still the sense that the winning ellipse is still different to how it might have been otherwise, a little wider, perhaps, or a little thinner from the effort of having to twist around the losing side. Do the other points notice, I wonder, do the other points tell each other stories of those that went down fighting, in past iterations, those that lost but still managed to make some small difference. Some small push in the direction they believed in. Do the points of the winning ellipse let themselves idly wonder, some evenings: what if they too could make such a difference? Moving stuff.
posted by eykal at 3:21 PM on December 3, 2012 [6 favorites]

That is very cool.

And what's even cooler is that the exact same process described in the linked paper, of repeated applications of a linear map ending up being a projection onto the principal eigenvector, explains this video: "Dueling Carls, a "Talking Carl" Scream Fight." In this case the eigenvector is an ellipse, in Carl's case the eigenvector is white noise.
posted by benito.strauss at 3:21 PM on December 3, 2012 [6 favorites]

Do the other points notice, I wonder, do the other points tell each other stories of those that went down fighting, in past iterations, ...

Probably yes, if you start out with 300 points.
posted by benito.strauss at 3:24 PM on December 3, 2012

The 45 degree thing makes no sense to me. The averaging process is invariant to rotation.

One theory: maybe the angle depends on the distribution you select your random points from. The square is not invariant to rotation. (I haven't checked this.)
posted by madcaptenor at 4:00 PM on December 3, 2012

Conjectures based on skimming the paper:

1. I *think* the 45 degree thing comes from the fact that x₁' = (x₁+x₂)/2. If instead, say, x₁' = (x₁+x₃)/2, then the leading eigenvalue arguments still hold, but we're looking at the angle between different roots of unity. Maybe.

2. This I feel more firmly about: Unless the angles of the initial polygon are all rational multiples of each other (ie with probability 0), then the limit cycle of polygons should be dense on the limiting ellipse.

It seems like you should be able to use an argument based on some equivalent of Jensen's inequality to arrive at the ellipse-converging part of the result. Might think on this over the weekend.
posted by PMdixon at 4:03 PM on December 3, 2012

Aha! The 45-degree alignment does not come from the averaging process at all! It comes from the fact that they are rescaling the x- and y-coordinates independently to have unit norm. As anyone who has resized pictures in PowerPoint without holding down Shift knows, this distorts the shapes of things!

Suppose the ellipse without rescaling would have looked like this (or a tiny version thereof). Then they'll just scale up the y-coordinates so their variance is exactly as big as the variance in the x-coordinates. Voilà, you get a 45-degree ellipse.

What they should do is rescale both x and y using the same scaling factor. This makes it a similarity transformation, i.e. it preserves aspect ratios. Then you'll get an ellipse in an arbitrary orientation, and it'll be rotation-invariant as expected.
posted by narain at 4:07 PM on December 3, 2012 [16 favorites]

Might the 45 degree thing have to do with this on the jasondavies.com page: Note that in the above demonstration, the scales are automatically adjusted with each step. I think the simulation is rescaling and rotating so that the shape is as big as possible while still fitting in the square - which for an ellipse will always be a 45 degree tilt between two corners. In the example here it doesn't tilt at all, though it does get a whole lot smaller, which might explain while the scaling is done on the other site.
posted by eykal at 4:09 PM on December 3, 2012

Yep, eykal, I just came to the same conclusion. Here's a fork of jjwiseman's code that preserves the aspect ratio.

What surprised me was that the paper makes the same -- maybe not mistake, but at least -- a questionable choice of rescaling.
posted by narain at 4:16 PM on December 3, 2012 [5 favorites]

I apologize if I'm posting too many comments. I forgot to mention: there's a really easy argument that the shape converges to an ellipse via the Fourier transforms of the x and y coordinates. Local averaging attenuates the higher frequencies more quickly, so after many iterations, the 0th frequency is the same (i.e. the mean doesn't change), and the 1st frequency is pretty small, but all the higher frequencies are negligible. This means that the x and y coordinates are just sinusoids, and that means that the points lie on an ellipse.
posted by narain at 4:30 PM on December 3, 2012 [9 favorites]

What happens with a set of points in 3D space?
posted by julianb at 4:59 PM on December 3, 2012 [2 favorites]

It comes from the fact that they are rescaling the x- and y-coordinates independently to have unit norm.

What? Savagery. You don't start a land war in Asia and you don't break the GL_2 symmetry.
posted by escabeche at 5:00 PM on December 3, 2012 [4 favorites]

julianb, my guess is that they would tend to an ellipse on a plane with an orientation dependent on the initial points.
posted by claudius at 5:38 PM on December 3, 2012 [2 favorites]

Connecting the midpoints iteratively is basically a kind of smoothing. Apply smoothing enough and you end up with a smooth curve.

This sentence makes me feel kinda funny, like when we used to climb the Möbius strip in math class.
posted by Riki tiki at 5:56 PM on December 3, 2012 [1 favorite]

narain, it seems like you need a step in that argument to show why the frequencies are the same, otherwise you'd get a Lissajous figure.

If that step held for three dimensions, then I think you would definitely get an ellipse on a randomly oriented plane.
posted by claudius at 5:59 PM on December 3, 2012

It's the lowest nonzero frequency, the one that completes a single oscillation from the 1st to the nth point. This holds for both x and y.

Also, I agree that the 3D case is an arbitrarily oriented ellipse embedded in 3 dimensions.
posted by narain at 6:10 PM on December 3, 2012 [1 favorite]

I was sort of hoping the 3D case would be an oblate spheroid, mainly because I like saying oblate spheroid.
posted by julianb at 6:29 PM on December 3, 2012 [1 favorite]

It probably would be an ellipsoid if the points were a closed connected surface.
posted by claudius at 6:37 PM on December 3, 2012

Protip: don't start with an equilateral triangle.

The first time I set it to 100 vertices, I let it run for 5 seconds or so. The rough shape that was produced wasn't an elipsis at all -- it was like an equilateral triangle with rounded corners. I let it run for another minute and it didn't change much, if at all. It achieved stasis like that, looking like nothing so much as a guitar pick, except the flat sides were equilateral and not isosceles (sorry to be loosey goosey with my terms here -- I've not taken math class in over a decade. I appreciate the patience of the mathematicians among you). I'm kicking myself for not screengrabbing it, but I was confused, since with 10 vertices it created an elipsis fairly quickly and when I re-ran it with 100, it eventually turned into a similar 45-degree oriented elipse. I've done it a dozen more times, and it always becomes an elipse eventually. I even changed it to 1000 points in Chrome as boo_radley suggested (fun!) -- it ended up looking more or less the same as the other two, which I gather is kind of the point.

So: How improbable is my guitar pick shape (and how great that I got it on my first try, right -- I thought I'd broken it!) If I'd let it run for an hour, or a thousand years, would the guitar pick become an ellipse, or was it something like an equilateral 100-point triangle, meaning that halving the sides would have no effect on the resulting polyhedron?
posted by andromache at 6:46 PM on December 3, 2012 [1 favorite]

On the off chance that anyone doesn't know what a guitar pick is shaped like. My peculiar shape was like that but all the legs of the "triangle" were the same length. But with the rounded corners like a pick. God, I need to learn what shapes are called.
posted by andromache at 6:49 PM on December 3, 2012

I've been doing some experiments in which I rescale x and y to the same scale; the ellipse comes out at all sorts of different angles. (If I had to guess I'd say that all orientations are equally likely - I'm actually starting with x and y random independent standard Gaussians so this should be true - but seriously, you guys actually want me to do work?)
posted by madcaptenor at 7:42 PM on December 3, 2012

I liked the paper---seems like a nice application of linear algebra to solve this cute geometry problem! Interesting observations y'all are making about the effect of the scaling factors on the final result.
posted by leahwrenn at 7:51 PM on December 3, 2012

This is neat and all, but what I really find fascinating are the optical illusions you can make yourself see when looking at the 100 node versions. You can trick yourself into believing that the balls are "traveling" in either direction. Also if you move your eyes at just the right speed, you can trick your brain into seeing a slow progression of balls instead of the rapid flow there actually is.
posted by Flunkie at 9:11 PM on December 3, 2012

Oh, also, for those of you who enjoy changing to "10" while a 100 is in progress: You can actually get that to happen over and over:

(1) Change to 100
(2) Start
(3) Change to 10
(4) "Randomise vertices"
(5) Goto (4)
posted by Flunkie at 9:15 PM on December 3, 2012

Start with three points on a plane and select one of them.

Randomly pick one of the original three points. Draw a new point at the midpoint, from that point, repeat.


Boom! Sierpinski Triangle


But y'all knew that.
posted by alex_skazat at 9:20 PM on December 3, 2012 [1 favorite]

If I'd let it run for an hour, or a thousand years, would the guitar pick become an ellipse...?

Yes indeed. Your guitar pick was approaching a circle, which is a kind of ellipse. It's just that the second harmonic hadn't decayed enough by then. (Take a look at this, then replace the 0.2's with gradually smaller values to see the, uh, destiny of the pick.)

God, I need to learn what shapes are called.

Oh, don't worry about it. There are more shapes in heaven and earth, Horatio, than are dreamt of in your dictionary. (Or anyone else's.)

Boom! Sierpinski Triangle

For the curious: this is known as the chaos game.
posted by narain at 9:40 PM on December 3, 2012

> Connecting the midpoints iteratively is basically a kind of smoothing. Apply smoothing enough and you end up with a smooth curve.

That isn't any form of proof; connecting the midpoints iteratively doesn't really "smooth" the curve in any real way (it always has exactly the same number of line segments and thus the same number of discontinuities, i.e. points where it isn't smooth at all), nor are "smoothings" in general guaranteed to converge to a fixed curve.

For example, consider the three dimension equivalent of taking the dual - joining the midpoints of the faces of a polytope. If you apply this to an icosahedron, you get a cycle of length 2 between icosahedron and dodecahedron - i.e. there's no limit at all.

The explanation is not so simple. From a skim of the paper, the first step is to represent the midpoint averaging process as a matrix transformation - a "linear transformation" that preserves lines, points and intersections. Matrices have what are called "eigenvectors" - in the direction of an eigenvector, a matrix operates like a simple linear scaling ratio. As you repeat this matrix operation, the vectors perpendicular to the line segments become more and more "rich" in this eigenvector, which is "why" the diagram converges to an ellipse, but you still need to prove that self-intersecting polygons tend to fix themselves so they don't intersect when you apply this operation repetitively.
posted by lupus_yonderboy at 10:56 PM on December 3, 2012

Oh, and my example above shows that there's no corresponding theorem for the 3-d case, unless there's some other "averaging" mechanism than the one I suggested which has it.

(If you don't like that example, the cube and the octahedron are also "dual" in that same sense...)
posted by lupus_yonderboy at 10:59 PM on December 3, 2012

To understand the smoothing properties of the map I think it could be interesting to look at a different representation of the polygon. Instead of listing the (x,y) of successive vertices, look at the (θ, d), where θ tells how much you turn at the vertex (compared to continuing the same direction you arrived there), and d measures how far you travel to the next vertex.

I'm sure the equations aren't pretty, but it'd be easy to see smoothing. The one big problem is that ellipses seem to be stable no matter how flat they are, and that means the θ value swings wildly at the sharp ends, and doesn't get smoothed out. I'll have to get out my old trig formulas.
posted by benito.strauss at 11:12 PM on December 3, 2012

lupus_yonderboy: if you look at the Elmachtoub paper, the matrices, and, in fact, the entire operation, work on the components in isolation. The three-dimensional analog isn't then a polyhedron, it's just an ordered set of n points in R³ with line segments connecting successive points. The hypothesis that narain and claudius are suggesting is that a similar algorithm, applied now to three vectors of components, will converge to an ellipse lying in an arbitrary plane. Note that the points were not initially coplanar in general.

However, since the operation works on independent components, projecting the resulting near-ellipse onto the XY plane will be the same as obtains from projecting the initial pointset there to begin with and proceeding in 2-d.

I don't see an obvious generalization to the case of a 3-d polytope since you'd need an additional assignment of faces to 3-lets of vertices. You need an equivalent number of faces to vertices or else the matrix formulation won't work. You could do something similar to the 2-d example by, say, taking the ith face to be defined by [r_i, r_i+1, r_i+2] (all indicies taken mod n). This obviously places restrictions on the sorts of polytope you could investigate, but might be interesting nonetheless.
posted by 7segment at 12:42 AM on December 4, 2012

Oh, hey, this is cool. narain, I love your perspective from harmonic analysis... intuitively the operation looks like a boxcar average and I kept trying to think of a way to bring the convolution theorem to bear. Better yet though, it looks as though the matrix formulation is well-studied:

In linear algebra, a circulant matrix is a special kind of Toeplitz matrix where each row vector is rotated one element to the right relative to the preceding row vector. In numerical analysis, circulant matrices are important because they are diagonalized by a discrete Fourier transform
posted by 7segment at 1:16 AM on December 4, 2012 [1 favorite]

That isn't any form of proof; connecting the midpoints iteratively doesn't really "smooth" the curve in any real way (it always has exactly the same number of line segments and thus the same number of discontinuities, i.e. points where it isn't smooth at all), nor are "smoothings" in general guaranteed to converge to a fixed curve.

Thank you, I wasn't offering a proof, merely making a comment that the result isn't unexpected. (Not to say that math isn't full of unexpected results, or that expected results don't need rigorous proof.) I'm sure there are many interesting pathological states, although, as pointed out above, the one you propose isn't quite what this paper is about.

More generally, I am not sure why I stayed up until 2:00 in the morning playing with this process when I had to be up at 7:00 for work.
posted by Nomyte at 6:15 AM on December 4, 2012 [1 favorite]

For example, consider the three dimension equivalent of taking the dual - joining the midpoints of the faces of a polytope. If you apply this to an icosahedron, you get a cycle of length 2 between icosahedron and dodecahedron - i.e. there's no limit at all.

Yes, but that's just a special case. I wouldn't be surprised to learn that if you take the dual of a random polyhedron repeatedly (for suitable definitions of "random") you end up with some limiting shape - and who knows, it might be an ellipsoid.

But I'm not coding that. Not for free.
posted by madcaptenor at 8:12 AM on December 4, 2012

And it certainly might be the case that if you start with some random set of 20 points which you join up by edges corresponding to those of an icosahedron, and then you iterate the icosahedron/dodecahedron dual game for a long time, you converge to something that's a linear transform of a regular icosahedron. This would have to do with the second-largest eigenvalue of some nice random walk on the vertices of the icosahedron I guess?
posted by escabeche at 12:57 PM on December 5, 2012

Damn you, escabeche, that's actually something I can code.
posted by madcaptenor at 2:42 PM on December 5, 2012