Wilson's Algorithm

That's because arcs are kind of like semi-random searches through air for a place that will equalize the voltage. See, for example, slow-motion videos of lightning: https://www.youtube.com/watch?v=7kI1d7DMbco

mrcactu5• 12 years ago

there is a mathematical link between random walks spanning trees and electrical networks

* http://www-math.mit.edu/~goemans/18434S11/RachelChasin-1.pdf

* RANDOM WALKS AND ELECTRIC NETWORKS Peter G. Doyle (Dartmouth), J. Laurie Snell (Dartmouth) http://arxiv.org/abs/math/0001057

niels_olson2• 12 years ago

Initially, the algorithm can be frustratingly slow to watch

By "frustratingly slow", what are we talking about? It's been running for over an hour with no progress and my computer at work automatically reboots over the weekend. How long do I need to keep this tab open?

jychang• 12 years ago

It finished in about 2 minutes for me, so you probably have a rendering issue. I'm on Chrome stable for Mac...

psychometry2• 12 years ago

It depends on whether a the algorithm can generate a sufficiently large path (the white line) at first, since further development requires the purple path intersect that fixed path.

niels_olson2• 12 years ago

Finally finished. Question: I see I can inspect the canvas element and even edit the code. How do I run it with my edits (without pushing it to a server?)

psychometry2• 12 years ago

Refresh your browser. I've had some that look like it'll take hours to complete and others than complete in 30 seconds.

somewhatjustin• 12 years ago

Is there a practical use for this algorithm, or is is simply for beauty?

fithisux• 12 years ago

You should consult literature.

Fuzzwah• 12 years ago

A print out of that would keep a small child entertained for a good amount of time....

coldtea• 12 years ago

For one, it creates a maze, right?

aet• 12 years ago

http://www.math.upenn.edu/~pemantle/papers/snell.pdf

dj-wonk• 12 years ago

I was looking for a nice visual explanation showing the connection between a maze and a spanning tree. I found this visual to be useful: http://cybertron.cg.tu-berlin.de/rapid_prototyping_11ws/maze...

mturmon• 12 years ago

The "Wilson" of the title is David Bruce Wilson (http://dbwilson.com), an accomplished mathematical probabilist, who may be familiar as a developer of perfect sampling ("Propp-Wilson") for Markov chain Monte Carlo computations.

guiambros• 12 years ago

Mike Bostock just showed this work last Wednesday at Eyeo Festival. It was a pure work of art.

The video of his talk will be posted next month to their Vimeo channel [1]; worth watching when it comes out.

[1] http://vimeo.com/eyeofestival

kernel_panic• 12 years ago

can you someone edit it and make it better? http://runnable.com/U5wQt8xHLYsVkYc_/wilson%E2%80%99s-algori...

jix• 12 years ago

Starting in a corner seems to be a worst case choice for a random walk on a non-looped grid. I forked it to

a) use a random order for starting (and restarting) http://bl.ocks.org/jix/30e55ae16b99efe94bfc/ab5a84881174512a... and

b) start from the center and always restart with the innermost free cell http://bl.ocks.org/jix/30e55ae16b99efe94bfc/aeaced224b45a413...

Wilson's Algorithm

Related Stories