“Geography, sir, is ruinous in its effects on the lower classes. Reading, writing, and arithmetic are comparatively safe, but geography invariably leads to revolution.”
(1879 testimony before a Select Committee of the House of Commons, London, England, regarding expenditures of the London School Board)
Monday, March 5, 2012
Map of the Week 3-5-2012:Craigslist meets Voronoi Tessellation!
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
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/
·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.