Map of the Week 3-5-2012:Craigslist meets Voronoi Tessellation!

Map showing Craigslist market territories, or Craigs-sheds, as we might call them.  From: http://uxblog.idvsolutions.com/2011/07/chalkboard-maps-united-states-of.html

I just had to make this a Map of the Week – and some of you faithful readers may know why.  That’s right!  Voronoi tessellations!  Delaunay triangulation!  Thiessen polygons!  Some of my very most favorite-est things!  Why do I love Voronoi diagrams so much?  They are so useful!  And elegant!  Put simply, a Voronoi diagram of a set of “sites” (points) is a collection of regions that divide up the plane.  Each region corresponds to one of the sites, and all the points in one region are closer to the corresponding site than to any other site.  It has applications in fields from anthropology to zoology, and just about everything in between.  A very simple yet effective interpolation technique.  

Delaunay triangulation on top of Voronoi diagram (in dotted lines), shows how they are constructed.   

“Voronoi diagrams were considered as early at 1644 by René Descartes and were used by Dirichlet (1850) in the investigation of positive quadratic forms.  They were also studied by Voronoi (1907), who extended the investigation of Voronoi diagrams to higher dimensions.  They find widespread applications in areas such as computer graphics, epidemiology, geophysics, and meteorology.  A particularly notable use of a Voronoi diagram was the analysis of the 1854 cholera epidemic in London, in which physician John Snow determined a strong correlation of deaths with proximity to a particular (and infected) water pump on Broad Street.”  From http://mathworld.wolfram.com/VoronoiDiagram.html

  

Snow considered the sources of drinking water, pumps distributed throughout the city, and drew a line labeled “Boundary of equal distance between Broad Street Pump and other Pumps,” which essentially indicated the Broad Street Pump's Voronoi cell. from: http://www.ams.org/samplings/feature-column/fcarc-voronoi

Some more recent examples:

A Delaunay triangulation surface to get an idea of what the spatial pattern was for the seismic activity in relation to the collapse of buildings after Haiti 2010 earthquake, from. http://geocommons.com/overlays/20545

A Delaunay Triangulation to determine the hierarchical spatial clustering of U.S. cities, from: http://www.ucgis.org/summer2002/guo/guo.html 

GP Practices in the UK, from http://danieljlewis.org/2011/01/18/spatial-design-for-gp-consortia/

Mobile phone location problem, from http://par.cse.nsysu.edu.tw/~homework/algo01/8834809/VoronoiD.htm

Voronoi tessellation based on world population density, from http://publib.boulder.ibm.com/infocenter/db2luw/v9/index.jsp?topic=%2Fcom.ibm.db2.udb.spatial.doc%2Fcsbgeo22.html

Coefficients of Representativity (CR) for 467 sample points in Switzerland, from http://publish.uwo.ca/~jmalczew/gida_7/Dubois/Dubois.htm  NOTE: this is quite interesting, if you like that sort of thing!

Visual estimation of sampling density with a Voronoi diagram.  Polygon size is determined by the proximity of pedon sampling locations (larger polygons = less dense sampling).  A “pedon” is the smallest unit or volume of soil that contains all the soil horizons of a particular soil type. From: http://casoilresource.lawr.ucdavis.edu/drupal/node/405

How the United States would look if Voronoi-ed, based on state capital cities as the points, from http://solar.physics.montana.edu/dana/.  It pretty much mirrors existing state boundaries, which only goes to show that the state capitals were located in the center of each state. 

Here’s a nice website on the Voronoi Game, which appears as a puzzle in the book Codes, Puzzles, and Conspiracy, where it is called the Territory Game and was inspired by the Falklands War.  From: http://www.voronoigame.com/

Some nice properties of the Delaunay triangulation (from http://www.ics.uci.edu/~eppstein/gina/scot.drysdale.html):

·         It's dual to the Voronoi diagram, so computing one automatically gives you the other.

·         The Empty Circle Property -- If you draw a circle through the vertices of ANY Delaunay triangle, no other sites will be inside that circle.

·         It's a planar graph. By Euler's formula, it has at most 3n-6 edges and at most 2n-5 triangles. This property can be used to reduce many problems with quadratic size (like closest pair) down to linear size in the time it takes to construct the triangulation.

·         It contains "fat" triangles, in the sense that the minimum angle of any Delaunay triangle is as large as possible. In fact, if you write down the list of all angles in the Delaunay triangulation, in increasing order, then do the same thing for any other triangulation of the same set of points, the Delaunay list is guaranteed to be lexicographically smaller.

For a discussion of their methods for developing the Craigslist sector map, see The IDV website, which claims to be “All things data viz, design, and geospatial” at http://uxblog.idvsolutions.com/2011/07/chalkboard-maps-united-states-of.html

The zipcodes within each Craigslist zone. For an update on their methods, see http://uxblog.idvsolutions.com/2011/12/craigszips.html

Couldn't resist this one!  Pretty!