Voronoi Diagramming and GIS

So in my entry on John Snow's cholera map, I accidentally stumbled upon the concept of voronoi diagramming.  I wanted to know more about voronoi, to understand it better, and have found some very interesting mathematical/geospatial websites and videos.  No, really- come back- it's really cool!

Okay.  So what is voronoi?  Here is more or less what I have absorbed, and my sincere apologies to any actual mathematicians in the crowd-- I am a moron.  Essentially picture a series of point data scattered on a page-- say, cities in the state of PA, or Duane Reade locations in NYC, or marbles scattered on a table top.  The voronoi diagram is generated by defining an irregular polygon around each point of data p whose border is defined by an equidistance between each other p, and therefore any point within the polygon will be closer to its own parent p point than any other point p.*  You will wind up with something fairly ugly, really, like this:

Voronoi Diagram

of course, in nature it's not so ugly.

Voronoi in dragonfly wing

Voronoi in turtle shell

To get the concept, just picture a dot in the center of each irregular polygon.  Voila!  Voronoi.

So, why am I posting this on a cartography blog?  Well, there are some pretty clear applications of Voronoi to GIS.  To go back to an earlier example I gave, Duane Reade locations in NYC (and there are ... about a million)...

You can't swing a dead cat in Midtown without hitting a Duane Reade, believe me.
View Larger Map

...picture a mapping query that allows you to block up NYC into polygons with data point centers p  that each represent a Duane Reade.  You can then take any other point on the island and immediately know its closest location to a Duane Reade, and route accordingly.

I found so much interesting material on Voronoi that I believe I will have to split this blog into two posts, and will have more to share tomorrow on Voronoi as it applies to GIS.  Until then....




*Another nice definition, if you prefer something a little cleaner than my idiot-savant distillation (because, really, you, like me, may need to read several different definitions before it really clicks), is: A Voronoi diagram divides the drawing into regions around each point that are shaped so that the borders of the regions are equidistant from the two nearest points. It's kind of the vector equivalent of grid mapping where you're trying to show boundaries of influence from point data.