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 mobile-friendly 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.

Steps for making a Voronoi diagram
Steps for making a Voronoi diagram
Credit Brent Jones | St. Louis Public Radio

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

Step 1: dots
Step 1: dots
Credit Brent Jones | St. Louis Public Radio

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

Step 2: Connect the dots
Step 2: Connect the dots
Credit Brent Jones | St. Louis Public Radio

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

Step 3: Find the center
Step 3: Find the center
Credit Brent Jones | St. Louis Public Radio

If you’re using two colors, switch colors. The next step is to use your ruler and find the mid-point 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 squared-off end of your ruler for this.

Step 3a: Create the bisectors
Step 3a: Create the bisectors
Credit Brent Jones | St. Louis Public Radio

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

Step 4: Trace the cells
Step 4: Trace the cells
Credit Brent Jones | St. Louis Public Radio

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.