Triangulation: Voronoi Diagrams

In this post, we will look at a practical problem: where should you open a new Blockbuster?

Before we begin, I should point out for younger readers that 'Blockbuster' was the name of a movie rental company that went bankrupt in 2010 and today has more or less ceased to exist (their Wikipedia page says that only private franchises still operate). I should also point out that 'movie rentals' were things that people did to watch movies before the existence of Netflix. For the purposes of this post, we will assume it is 2003, when Blockbuster was making a lot of money and doing well as a company, so they were actually opening new stores instead of shutting down old ones.

You have been asked to select the site of a new Blockbuster store in an existing city with several stores already open. In the real world, there are a lot of different factors that influence this decision: population density, property costs, transportation accessibility and competitors being just four I could come up with off the top of my head. For this post, we will consider only the three tenets of real estate: location, location, and location.

All else being equal, a Blockbuster customer will go to the closest store to their home. They will also not go to Blockbuster at all if the closest store is still further away then their Laziness Quotient. (Incidentally, a large part of the reason that Netflix destroyed Blockbuster was that it reduced the Laziness Quotient of nearly everyone to essentially zero.) This suggests that our new store should be selected to be as far away as possible from other stores. This will maximize new customers, and minimize duplicate coverage, which does not give you any new business. (As an extreme example, if your new location was across the street from an existing store, you would succeed in getting zero new customers, and have two stores that were only doing half as much business as the old one did.)

To solve this problem, you begin by taking a map of your store locations, and assigning each location a colour:

You then colour the rest of the map according to the following rule: the colour at a given point should be the same colour as the closest store:

The resulting image is known as a Voronoi diagram, after some mathematician named Voronoi. It can be used as the basis of a solution for the 'nearest neighbour' problem: given a point, which of a set of points is closest? If you were to pin a Voronoi diagram to a wall and throw a dart at it, the colour it hits would correspond to the nearest neighbour answer. Each region of colour shall be called the Voronoi cell for a given point, called a Voronoi site.

It is not difficult to prove that at the border between two cells, called a Voronoi edge, the distance between that border and the two sites is equal. It is also not difficult to prove that at the points where three or more cells meet, called a Voronoi vertex, the distance between that point and the cell's sites are all equal. Astute readers will immediately note that this sounds an awful lot like the circumcircle of the points.

The answer to the problem, therefore, is to pick the Voronoi vertex with the largest circumcircle of the original points, and open the new Blockbuster at that point.

Readers of the blog will note an uncharacteristic finality in that answer. Surely, I am going to go on to other special cases, or places where that approach does not work? I am not. I have already noted that this approach ignores a whole host of other urban planning factors, but in terms solely of location, it is the best choice.

I will, however, go on to note that Voronoi diagrams have a whole host of uses. One of the most interesting ones to me was its use in one of the founding experiments of epidemiology. In 1854, there was a serious cholera epidemic in London. Back then, the cause of cholera (a bacterial infection) was not known. A physician by the name of John Snow, usurping George R. R. Martin by over a century, was trying to determine a cause, or cure, or treatment to the epidemic. His great insight led him to take a map of London, and to overlay a Voronoi diagram generated by using the locations of water pumps as the sites. He then plotted the homes of all of the infected and deceased victims of the epidemic. Nearly all of the infected were within a single Voronoi cell: that of the Broad Street water pump. The evidence that this pump was responsible was strong enough that the city council had the water pump's handle removed to prevent further transmission of the disease.

As mentioned above, Voronoi diagrams can be used to efficiently compute nearest-neighbour operations, which are common in geometric algorithms. They can also be used as a texture-generating primitive, in similar fashion to the more well-known Perlin noise, which is the video game development application of choice for this blog.

Finally, the diagrams make for pretty pictures. The joke in 'A Brief History of Time' is that each formula would halve the readership of Stephen Hawking's novel; my hope is that each Voronoi diagram I add to my posts will double its readership.

In the next post, I will reveal the terrible secret connecting Voronoi diagrams to point set triangulation.