Math Geekery

September 16, 2009 5:37 AM

For math geeks. How to Draw the Voronoi Diagram. Voronoi diagrams, as a geometric model are fascinating because they can be used to describe almost literally everything: from cell phone networks to radiolaria, at every scale: from quantum foam to cosmic foam. See also the Wallpaper Group: there are only 17 ways to fill a plane with a regular 2 dimensional pattern. Fred Scharmen [weblog home] is known as 765 and also produces a number of shapes, textures and patterns.
posted by netbros (35 comments total)

Humans are awesome.
posted by vapidave at 6:17 AM on September 16, 2009

For math geeks. How to Draw the Voronoi Diagram.

if you're a math geek, you already know how.
posted by lester at 6:55 AM on September 16, 2009

This is relevant to my interests.
posted by limited slip at 6:56 AM on September 16, 2009

This Voroni toy (Flash 10) is very fun, once you grok the keyboard controls: http://nodename.com/blog/2009/05/11/a-voronoi-toy/

(Click the image to launch the toy.)
posted by ericost at 7:01 AM on September 16, 2009 [6 favorites]

Brian Knep made a really beautiful piece of interactive video art using this:
Voronoi Diagrams at the Milwaukee Art Museum (self-link)
posted by escabeche at 7:03 AM on September 16, 2009 [1 favorite]

lester: I'm a math geek, and I didn't know how.
posted by madcaptenor at 7:15 AM on September 16, 2009

Voronoi tessalations are remarkably useful, and a powerful tool in some surprising circumstances. The dual graph - the Delaunay triangulation - is very handy for building networks between points. This tale of slow IDL loops is one example of how the triangulation achieves boggling speedups (for the unusual case of an initially bafflingly slow approach).
posted by edd at 7:17 AM on September 16, 2009 [1 favorite]

Instant Vector Crystal (bath) Foam makes a nice valentines gift for that special hippy someone on valentines day.
posted by idiopath at 7:19 AM on September 16, 2009

As San Francisco's Exploratorium, they have this floor area people can walk around on. A projector on the ceiling puts an image in the floor area of Voronoi looking diagrams of shapes around the people. If there are more people, then you get more shapes. Walking around it is like holding the mouse button down in the Voroni toy ericost mentions.

Kids love to run around watching their pattern follow them around, constantly changing shape.
posted by eye of newt at 7:24 AM on September 16, 2009

MeTa

I actually hope this is the blog post sidereal was talking about. If not maybe he will come here and post it. I am not a math geek so all this is new to me but it is interesting stuff that I would never have learned if not for MetaFilter. Great post, netbros!
posted by TedW at 7:32 AM on September 16, 2009

TedW: Since Fred Scharmen's Flickr contacts include sidereal, and vice-versa, I'd say the likelihood is pretty high this is the post. Also, really, how many blog posts about Voronoi Diagrams are there likely to be in a given month?
posted by cerebus19 at 8:01 AM on September 16, 2009

this was on snarkmarket a few days ago. great and beautiful stuff. i can't wait until i get time to finish my voroni based music visualizer.
posted by localhuman at 8:05 AM on September 16, 2009

More Math + Art Geekery with Voronoi diagrams: http://moebio.com/loveispatient/
posted by ericost at 8:17 AM on September 16, 2009 [2 favorites]

I screwed up -- the Voronoi piece in Milwaukee was Scott Snibbe's Boundary Functions. Looks like this has also been shown at the Exploratorium, so it must be what eye of newt saw.
posted by escabeche at 8:17 AM on September 16, 2009

How to draw a voronoi diagram in Photoshop

Simulating Voronoi Diagrams with Photoshop Lighten Blend Mode
posted by jfrancis at 8:23 AM on September 16, 2009 [2 favorites]

The 17 wallpaper groups are fun to explore in Artlandia SymmetryWorks - ImageSkill TileBuilder and other programs
posted by jfrancis at 8:27 AM on September 16, 2009

Fascinating. I had never heard of Voronoi diagrams.

I'm thinking that flagstone patio I have planned for the weekend is about to become a lot more complicated!
posted by Kabanos at 8:27 AM on September 16, 2009

Not a math geek, but would would love to be one: Is there a relationship between Voronoi diagrams and the Traveling Salesman Shortest Route problem?
posted by Xoebe at 8:39 AM on September 16, 2009

I love my Voronoi and Delaunay triangulations, and use this a lot in my paper artwork (making, of all things, tessellations.)

There's something seriously beautiful about the way these things work, and how you can draw so many parallels to all things in nature just by looking at abstract voronoi cells.

I came up with a methodology to fold any given voronoi tiling out of paper, which really made me fall in love with the process, even though it's a bit cumbersome.

The software tools to play with voronoi tessellations make me get lost for *hours* and I totally geek out over it.

This is by far some of the best of the web, thanks so very very much for posting!
posted by EricGjerde at 8:46 AM on September 16, 2009

The Voronoi Diagram sounds like a Clive Cussler novel.
posted by adamdschneider at 8:52 AM on September 16, 2009

Is there a relationship between Voronoi diagrams and the Traveling Salesman Shortest Route problem?

No, not really. The Voronoi diagram is the dual graph of the Delauney triangulation of the same set of points. It was once thought that the Delauney triangulation might always contain the solution to the Euclidean Traveling Salesman Problem on that point set, but it turns out that it does not.
posted by jedicus at 8:57 AM on September 16, 2009

Sand falling through holes forms a Voronoi diagram
posted by jfrancis at 9:10 AM on September 16, 2009 [4 favorites]

His blog is beautiful. I could read it all day long. This entry is somehow poetry and bike advocacy and a sort of present-day urban anthropology all at once without the sloppiness implied by any of those.
posted by sleevener at 9:30 AM on September 16, 2009 [1 favorite]

From the linked article: If everything has been done correctly, there will always be three lines converging at a point, unless the input sites are on a perfectly regular rectangular grid. Drawing the last line of the three and watching it land exactly where it's supposed to is extremely satisfying. Watching it miss can mean going back all the way to step two and flipping the Delauney graph for the triangle.

Er, no. The perpundicular bisectors of any triangle meet at a single point; it is not, as this statement would seem to imply, true only of triangles in the Delauney triangulation. If the three perpundicular bisectors you draw for a given triangle do not meet at a single point, that indicates only that you have not drawn them carefully enough and says nothing one way or the other about whether your prospective Delauney triangulation is correct.

That said, an eyeballed approximate Delauney triangulation is probably good enough for most applications—particularly artistic ones—even if it's not the true Delauney triangulation.

The Voronoi diagram is the dual graph of the Delauney triangulation of the same set of points. It was once thought that the Delauney triangulation might always contain the solution to the Euclidean Traveling Salesman Problem on that point set

I came up with that hypothesis on my own once; I was pretty pleased with myself when I disproved it by finding a counterexample consisting of only five points.
posted by DevilsAdvocate at 9:45 AM on September 16, 2009

gahd, so much time that I spend in the mid-90s trying to write code to do Delaunay triangulations and voroni diagrams. It's tricky stuff to do from scratch.
posted by GuyZero at 9:58 AM on September 16, 2009

Voronoi animation.
Made with Processing. Audio by Kruder and Dorfmeister (Hide Abstract Jazz).
posted by Kabanos at 10:00 AM on September 16, 2009

there are only 17 ways to fill a plane with a regular 2 dimensional pattern

18 -- you forgot to include "filling it with bacon."
posted by msalt at 10:20 AM on September 16, 2009

there are only 17 ways to fill a plane with a regular 2 dimensional pattern

But there are always Penrose tilings. I don't think there any proof that there are a finite number of those.
posted by GuyZero at 10:46 AM on September 16, 2009

I've fiddled with Voronoi diagrams and music, and wrote a paper about it here:
http://doc.gold.ac.uk/soundvis/papers/mclean-Apollonius.pdf
posted by yaxu at 11:08 AM on September 16, 2009 [1 favorite]

penrose tilings are Aperiodic...therefore, not regular.
posted by sexyrobot at 11:54 AM on September 16, 2009

There are actually an infinite number of Penrose tilings, but these are not in the same class as the 17 members of the Wallpaper Group, all of which exhibit translational symmetry. Penrose tilings do not.
posted by Songdog at 11:54 AM on September 16, 2009

Yay! Yes, this is the one I wanted to post, but it's the blog of a personal friend. Kudos, netbros!
posted by sidereal at 1:11 PM on September 16, 2009

Yes, escabeche Boundary Functions is what was at the Exploritorium. They also had a small one in which you put pieces on this board and it creates the patterns.

I would think that this would offer a solution to the picocell femtocell problem. Basically phone companies and WiMax companies want to set up all these cell base stations. Each one can only handle so much traffic, so you need more of them in a crowded area. femtocells are cell base-stations that you put in your house. If they can get enough people to install these they can get added density in crowded areas. But how do you get all these randomly added base stations from not interfering with each other? They need to self-assemble and only broadcast enough power on the appropriate frequencies to not overlap.

Sounds like an almost impossible problem, until you walk around the Boundary Function floor, and watch this problem being solved in real time with rapidly moving objects (people).
posted by eye of newt at 7:37 PM on September 16, 2009

We once used the Voronoi polygons to probe the effects of competition in plants, studying individual-to-individual interference between and among buttercups living in situ. The real novelty to the study was that it was based on natural populations ---novel in that nearly all plant competition studies are based on density manipulations, planting rows and grids of 10X, 100X, 1000X, etc. and observing the differences. The literature on competition is vast, and deep, but deeply narrow (is that the fox or the hedgehog?). For us ---me and, importantly, a student who was a math-geek-modeler (and he might, may-hap, have modeled math geeks had he been inclined), the Voronoi polygons could be fitted post-facto to detailed demographic data and then 'sorted' statistically. They were a powerful tool in seeing certain of the plant responses to crowding. As I recall, a social effect was suggested..
posted by JL Sadstone at 12:24 PM on September 17, 2009

I know this comment is late, but...

McVoronoi
Voronoi diagram illustrating the distance to the nearest McDonalds in the US.
posted by Kabanos at 1:31 PM on September 25, 2009 [1 favorite]