Now Playing
Connect with Us
Podcasts & RSS Feeds
All Content 
 RSS 
View all podcasts & RSS feeds 
Voronoi Diagram
2:56 pm
Fri August 8, 2014
How We Made Our STL 250 Cake Map
Find your closest cake.
Use the map above (or click here for a larger or mobilefriendly version) to find out which cake is closest to you, or explore different categories of cakes. Each dot represents a cake sculpture. The shape created by the black lines represents the area that is closer to that cake than any other cake sculpture. Click on any location to find out where the nearest cake is and some information about it.

When Cityscape producer Alex Heuer came to me with a question about doing something to map the STL 250 cakes, I immediately thought of a Voronoi diagram.
For the uninitiated, a Voronoi diagram is a mathematic method for dividing space. You start with a set of points — for example, cell phone towers, fire stations or, in this case, statues of cakes. Then, using math, you divide the space up to find the area around each point that is closer to that point than any other.
Let’s use doughnut shops, for example. If you found the locations of all the doughnut shops in St. Louis and calculated the Voronoi diagram, you’d be able to see the nearest doughnut shop to any given location. You could also find the doughnut shop serving the largest area. Further, you could find what mathematicians call the “largest empty circle” to find an optimal place to build your new doughnut shop so that it will be as far away as possible from all existing doughnut shops.
People are using Voronoi diagrams in all sorts of interesting ways: Jason Davies built a Voronoi diagram of the world’s airports and Noah Veltman built one for the major league teams in baseball, football, basketball, hockey and soccer.
Create your own!
You can create your own simple Voronoi diagram with only paper, a ruler and a pen or pencil. It helps to have two different colors of ink or lead, because we’re actually going to build what’s called the Delunay triangulation first.
Step 1: Get your points
You need a set of random points on the page. You can create them yourself, but if you’d like to be more methodical, one suggestion is to sprinkle a few grains of pepper, salt or sugar over the page, and marking where they fall.
You don’t want too many of these: The more spots you have, the longer it will take you to make the diagram.
Step 2: Create the Delunay triangulation
That sounds complicated, but it really means “connect the dots.” But there’s one caveat: No lines should cross. You want to connect each dot with all the other dots around it, but not cross any lines.
Start by connecting all the dots around the “outside,” so you have a ring containing all your other dots. Then start connecting points on the inside, choosing points to make your lines as short as possible.
Step 3: Mark center points and draw bisectors
If you’re using two colors, switch colors. The next step is to use your ruler and find the midpoint of the lines you just drew. Do this for all the lines before proceeding.
Now, using those midpoints, draw a line at a right angle, bisecting the lines from step 2. You can use a protractor, right angle or even the squaredoff end of your ruler for this.
If you’ve done this correctly, you will always have three of these lines meeting at a point (unless your starting points are in some weird shape, like a perfect grid).
Step 4: Trace the Voronoi cells
Take a look at your drawing and focus on the lines from step three. You should see the Voronoi grid. You can trace them to make them more apparent.
And now, you’re done. Each cell shows the area on the page closer to the dot inside it than any other dot.
Or do it digitally
But of course, we didn't do this by hand for 251 cakes. And Jason Davies certainly didn't do it for all the airports of the world.
Instead, this is something that computers are really good at. There are many ways to create a Voronoi diagram with a computer. We used a javascript library called d3.js. Here's an example of an interactive Voronoi diagram by that library's creator, Mike Bostock.

Cityscape