death_map_2008_upg
death_map_2008_upg,
"The Death Map",
a talk given at the University of Pittsburgh at Greensburg (UPG)
on 14 November 2008 to an undergraduate audience,
sponsored by Professor Gary Hart.
Despite the gruesome title, the subject was primarily
Voronoi diagrams, with a little information on their
properties and construction, and the creation of "centered"
or "centroidal" Voronoi diagrams.
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.
Reference:
-
The John Snow web site
maintained by the UCLA School of Public Health at
http://www.ph.ucla.edu/epi/snow.html.
-
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.
-
Franz Aurenhammer,
Voronoi diagrams -
a study of a fundamental geometric data structure,
ACM Computing Surveys,
Volume 23, Number 3, September 1991, pages 345-405.
-
George Barlow,
Hexagonal Territories,
Animal Behavior,
Volume 22, 1974, pages 876-878.
-
John Byers,
Dirichlet Tessellation of Bark Beetle Spatial Attack Points,
Journal of Animal Ecology,
Volume 61, 1992, pages 759-768.
-
John Byers,
Correct Calculation of Dirichlet Polygon Areas,
Journal of Animal Ecology,
Volume 65, 1996, pages 528-529.
-
Marc deBerg, Marc Krevald, Mark Overmars,
Otfried Schwarzkopf,
Computational Geometry,
Springer, 2000,
ISBN: 3-540-65620-0,
LC: QA448.D38.C65.
-
Qiang Du, Vance Faber, Max Gunzburger,
Centroidal Voronoi Tessellations: Applications and Algorithms,
SIAM Review,
Volume 41, Number 4, December 1999, pages 637-676.
-
Herbert Edelsbrunner,
Geometry and Topology for Mesh Generation,
Cambridge, 2001,
ISBN: 0-521-79309-2,
LC: QA377.E36.
-
Sandra Hempel,
The Strange Case of the Broad Street Pump,
University of California, 2007,
ISBN13: 978-0520250499,
LC: RA644.C3.H46.
-
Christian Icking, Rolf Klein, Peter Koellner, Lihong Ma,
A Java Applet for the Dynamic Visualization of Voronoi Diagrams,
https://www.pi6.fernuni-hagen.de/GeomLab/VoroGlide
-
Steven Johnson,
The Ghost Map,
Riverhead, 2006,
ISBN-13: 978-1594489259,
LC: RC133.G6.J64.
-
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.
-
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.
-
Joseph ORourke,
Computational Geometry,
Second Edition,
Cambridge, 1998,
ISBN: 0521649765,
LC: QA448.D38.
-
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.
-
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.
-
multimedia.sty, a LaTeX style file;
-
icam_logo.pdf,
a PDF image of
a logo for Virginia Tech's Interdisciplinary Center for Applied Mathematics (ICAM).
Graphics Files
-
causeway1.png,
an image of the Giant's Causeway, showing how the hexagonal
pillars seem to form a staircase into the ocean;
-
causeway2.png,
an image of the Giant's Causeway from above, emphasizing the
roughly equal size and hexagonal shape of the "tiles", and
the irregularity of the pattern;
-
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.
-
cube.png,
an image of a 3D cube, to illustrate Euler's Formula for
bounded polyhedrons.
-
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.
-
diamond_mountains.png,
a "mountain" plot of the diamond points shows the generators
as peaks, and the diagram lines as straight valleys, generated
by
VORONOI_MOUNTAINS.
-
diamond_pixel_plot_l1.png,
a pixel plot of the Delaunay triangulation of the diamond points,
generated by
VORONOI_PLOT, using the L1 distance. Some "mistakes" in the
plot are actually caused by the fact that for the L1 distance,
the boundary can consist of an area, rather than a line, that
is, for certain generators, a relatively huge (and area filling)
number of points can be equidistant from two generators. The plotting
routine doesn't spot this, but its results suggest what is happening.
-
diamond_pixel_plot_l2.png,
a pixel plot of the Delaunay triangulation of the diamond points,
generated by
VORONOI_PLOT, using the L2 distance.
-
diamond_points.png,
a set of 9 points, whose Voronoi diagram includes a "diamond",
generated using MATLAB.
-
diamond_voronoi.png,
the Voronoi diagram of the diamond points,
generated using MATLAB.
-
different_maps.png,
shows that, without the correct organizing principle, the
explanation for the cholera death data can be invisible.
-
drying_mud.png,
a photograph of drying mud shows a pattern of cracks which
suggests a Voronoi pattern, except that the mud drying is a
slow process, and the initial patterns seem to divide further
as the process proceeds.
-
giraffe.png,
a photograph of a giraffe shows the distinctive pattern
of patches that have some features of a Voronoi diagram.
-
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
https://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
https://www.epi.msu.edu/johnsnow/index.html.
-
hundred_points.png,
a hundred points chosen randomly in the unit square,
generated using MATLAB.
-
hundred_voronoi.png,
a plot of the Voronoi diagram of the hundred points,
generated using MATLAB.
-
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.
-
random_mountains.png,
a "mountain" plot of a set of random points, tilted a bit, and
with a banded color map to emphasize contours, generated
by
VORONOI_MOUNTAINS.
-
star.png,
the figure of a star, used to illustrate Euler's formula.
-
tilapia_birth.png,
a photograph of tilapia "giving birth", showing why they
are called "mouthbreeders";
-
tilapia_nest.png,
a photograph of tilapia nests in a sandy bottom, from the paper
by Barlow.
Last revised on 02 February 2024.