VT_2009.TEX
The Death Map

I gave a talk at Virginia Tech on 10 November 2009, to a group of students from Hollins University whose teacher was Professor Patricia Hammer. The talk was titled

The Death Map

Abstract:

The markings on giraffes are an example of a peculiar kind of irregular pattern that recurs in many other situations, including cracks in drying mud, the territories of competing "tribes" of fire ants, and the network of discrete churning "cells" in boiling liquid. A mathematical structure can be abstracted from these different cases, and used to classify and understand new problems as well. The Voronoi diagram is one tool of the field of computational geometry, a subject you didn't study in high school! We will suggest some areas where the Voronoi diagram can provide insight, we will suggest some of its mathematical properties, talk about its extensions to other geometries, distances and dimensions. We will show a special kind of Voronoi diagram that arises when the defining center points are allowed to adjust themselves, and we will show how random numbers can be used to approximate this shape.

PDF Version:

A PDF version is available as ../../presentations/vt_2009.pdf

Reference:

1. The John Snow web site maintained by the UCLA School of Public Health at http://www.ph.ucla.edu/epi/snow.html.
2. Eldridge Adams,
   Territory Size and Shape in Fire Ants: A Model Based on Neighborhood Interactions,
   Ecology,
   Volume 79, Number 4, June 1998, pages 1125-1134.
3. Franz Aurenhammer,
   Voronoi diagrams - a study of a fundamental geometric data structure,
   ACM Computing Surveys,
   Volume 23, Number 3, September 1991, pages 345-405.
4. George Barlow,
   Hexagonal Territories,
   Animal Behavior,
   Volume 22, 1974, pages 876-878.
5. John Byers,
   Dirichlet Tessellation of Bark Beetle Spatial Attack Points,
   Journal of Animal Ecology,
   Volume 61, 1992, pages 759-768.
6. John Byers,
   Correct Calculation of Dirichlet Polygon Areas,
   Journal of Animal Ecology,
   Volume 65, 1996, pages 528-529.
7. Marc deBerg, Marc Krevald, Mark Overmars, Otfried Schwarzkopf,
   Computational Geometry,
   Springer, 2000,
   ISBN: 3-540-65620-0,
   LC: QA448.D38.C65.
8. Qiang Du, Vance Faber, Max Gunzburger,
   Centroidal Voronoi Tessellations: Applications and Algorithms,
   SIAM Review,
   Volume 41, Number 4, December 1999, pages 637-676.
9. Herbert Edelsbrunner,
   Geometry and Topology for Mesh Generation,
   Cambridge, 2001,
   ISBN: 0-521-79309-2,
   LC: QA377.E36.
10. Sandra Hempel,
    The Strange Case of the Broad Street Pump,
    University of California, 2007,
    ISBN13: 978-0520250499,
    LC: RA644.C3.H46.
11. Christian Icking, Rolf Klein, Peter Koellner, Lihong Ma,
    A Java Applet for the Dynamic Visualization of Voronoi Diagrams,
    http://www.pi6.fernuni-hagen.de/GeomLab/VoroGlide
12. Steven Johnson,
    The Ghost Map,
    Riverhead, 2006,
    ISBN-13: 978-1594489259,
    LC: RC133.G6.J64.
13. Lili Ju, Qiang Du, Max Gunzburger,
    Probabilistic methods for centroidal Voronoi tessellations and their parallel implementations,
    Parallel Computing,
    Volume 28, Number 10, October 2002, pages 1477-1500.
14. Atsuyuki Okabe, Barry Boots, Kokichi Sugihara, Sung Nok Chiu,
    Spatial Tessellations: Concepts and Applications of Voronoi Diagrams,
    Second Edition,
    Wiley, 2000,
    ISBN: 0-471-98635-6,
    LC: QA278.2.O36.
15. Joseph ORourke,
    Computational Geometry,
    Second Edition,
    Cambridge, 1998,
    ISBN: 0521649765,
    LC: QA448.D38.
16. Robert Renka,
    Algorithm 772: STRIPACK: Delaunay Triangulation and Voronoi Diagram on the Surface of a Sphere,
    ACM Transactions on Mathematical Software,
    Volume 23, Number 3, September 1997, pages 416-434.
17. Peter Vinten-Johansen, Howard Brody, Nigel Paneth, Stephen Rachman, Michael Rip,
    Cholera, Chloroform, and the Science of Medicine: A Life of John Snow,
    Oxford University Press, 2003,
    ISBN: 019513544X,
    LC: RA649.5.S66.S647.

TeX "Source Code"

The following files constitute the LaTeX file:

• cholera.png, an image of the cholera bacteria.
• cholera_art.png, an imaginative piece of artwork showing the spread of cholera, which also illustrates the belief that it was spread through "bad air";
• cholera_spread.png, a map of the world, showing the spread of cholera during the seventh pandemic.
• cvd_01.png step 1 in a CVT calculation.
• cvd_02.png step 2 in a CVT calculation.
• cvd_03.png step 3 in a CVT calculation.
• cvd_04.png step 4 in a CVT calculation.
• cvd_05.png step 5 in a CVT calculation.
• cvd_10.png step 10 in a CVT calculation.
• cvd_15.png step 15 in a CVT calculation.
• cvd_20.png step 20 in a CVT calculation.
• cvt_circle_nonuniform_step50.png, an image of a CVT calculation on a circle with a nonuniform density.
• cvt_movie2_0001.png, frame 1 of an animation of a CVT computation in the square. For the whole movie, refer to CVT_MOVIE2.
• cvt_movie2_0002.png, frame 2 of an animation of a CVT computation in the square.
• cvt_movie2_0010.png, frame 10 of an animation of a CVT computation in the square.
• cvt_movie2_0020.png, frame 20 of an animation of a CVT computation in the square.
• cvt_movie2_0040.png, frame 40 of an animation of a CVT computation in the square.
• cvt_movie2_0080.png, frame 80 of an animation of a CVT computation in the square.
• different_maps.png, shows that, without the correct organizing principle, the explanation for the cholera death data can be invisible.
• ghostmap_cover.png, the cover of Steven Johnson's "The Ghost Map".
• golden_square.png, a map of the Golden Square area, where a highly localized outbreak of cholera occurred in 1854, from the John Snow archive and research companion site at http://www.epi.msu.edu/johnsnow/index.html.
• golden_square_detail.png, a detail of the Golden Square map, showing the suspected pump, and a dotted line around its "neighborhood", from the John Snow archive and research companion site at http://www.epi.msu.edu/johnsnow/index.html.
• john_snow.png, an image of Dr John Snow.
• p36.txt, the coordinates of 36 points.
• p36_points.png, an image of 36 points.
• p36_voronoi.png, an image of the Voronoi diagram of 36 points.
• p9.txt, the coordinates of 9 points.
• p9_points.png, an image of 9 points.
• p9_voronoi.png, an image of the Voronoi diagram of 9 points.
• pixel_10.png the output of the command pixel_plot(10,10).
• pixel_100.png the output of the command pixel_plot(100,100).
• pixel_1000.png the output of the command pixel_plot(1000,1000).
• pixel_plot.m a command to make a pixel plot of the Voronoi diagram of the 9 points.
• pump_memorial.png, a photograph of the John Snow memorial in Broad Street, which is a replica of the pump he identified as the source of the epidemic.
• pumps_map.png, a map of the locations of pumps and deaths in the Golden Square cholera epidemic.
• pumpwomen.png, a drawing of the Broad Street Pump, suggesting how local women collected water in pumps for use at home.
• sphere.png, an exact Voronoi diagram on a sphere.
• sphere_generators.png, Voronoi centers on a sphere.
• sphere_voronoi.png, an approximate Voronoi diagram on a sphere.
• strange_case_cover.png, the cover of Sandra Hempel's "The Strange Case of the Broad Street Pump".
• usa_voronoi.png, the USA after the state capitals were moved to the state centroids, and then states were replaced by Voronoi cells.
• voronoi_torus.png, a Voronoi diagram on a torus.
• vt_2009.tex, the LaTeX source;
• vt_logo.pdf, a logo.

You can go up one level to the LATEX home page.