What's a Voronoi Diagram?

[Note: I've made a Jupyter Notebook (Python) for this so that you can mess around with a few of these ideas yourself. The figures come from this notebook.]

⚫ ⚫ ⚫ ⚫

Let me tell you a story, reader. Back in the days of old there was a King who had five sons who did not get along with each other. When the King died, he left his five sons five different homes in the countryside where no one else lived.

The brothers hated each other so much that each of them began building fences between each other. But, if the fence was closer to one brother than the other, the brother that it was closer to would knock it down right away because they wanted to fence in the most land possible. Because of this, the brothers had to fence in only land which was closest to them and no other brother.

The ultimate divisions that the brothers created is called a Voronoi Diagram. There's a ton of cool things that happen with these, but let's see one example of a nice Voronoi diagram with the five brothers. We'll talk about what it means after the figure.

Note that each blue point (the brothers) are either enclosed in a polygon or are in a large, infinite region separated by others by the dotted lines (these are still actually polygons if we include a point at infinity, or simply say that the edge of the graph are the other parts of the enclosed polygon). These polygons are usually called Voronoi Cells and there is exactly one point in our input in each Voronoi cell. Usually, these areas are colored in various colors to help distinguish one from another — alas, the writer does not know how to make matplotlib and bokeh play nice with the Voronoi plotter so the reader will have to do without.

Notice that, for example, the center two blue points in the two polygons with solid edges. Each point (on the plane, not just in the input points) in the triangle is closer to the blue point than to any other blue point. For example, the point $$(0, 0.7)$$ is closest to the blue point in the triangle, but $$(0, 1)$$ is actually closer to the point directly above it, since that point is in the top-left Voroni cell (with the dotted lines).

⚫ ⚫ ⚫ ⚫

Voronoi diagrams can become fairly complex, as the next plot shows:

And this is a relatively nice one! Sometimes one makes a Voronoi diagram with hundreds of thousands of points, creating an enormous web-like monstrosity.

They're a nice thing to keep in your head as part of your math toolkit. As we'll see when we do K-Means Clustering, they can show up in unexpected places.