VT_2005.TEX
The Poison Pump and the Spitting Fish

I visited Virginia Tech, and gave a talk there, on 26 April 2005, to the student chapter of SIAM. The talk was titled

The Poison Pump and the Spitting Fish

A brief abstract of the talk is:

Discrete geometry looks at the relationship of points and space. The simplest tools for this analysis include the convex hull, the Voronoi diagram, and the Delaunay triangulation. These objects can readily organize and explain many facts of everyday life, from cholera outbreaks to the mating behavior of fish. In this talk, we will concentrate on the Voronoi diagram, defining it, explaining how it can be computed by hand or on the computer. We will even show how it can be computed (approximately) using random numbers. We will mention applications including coding theory, approximate quadrature, sampling, and mesh generation.

A longer abstract is available as a LaTeX file in

• vt_2005_abstract.tex, the LaTeX source;
• a PDF version;

The LaTeX file used to create the presentation employs the Beamer class.

Some references for the talk include:

1. Franz Aurenhammer,
   Voronoi diagrams - a study of a fundamental geometric data structure,
   ACM Computing Surveys,
   Volume 23, Number 3, September 1991, pages 345-405.
2. George Barlow,
   Hexagonal Territories,
   Animal Behavior,
   Volume 22, 1974, pages 876-878.
3. Marc deBerg, Marc Krevald, Mark Overmars, Otfried Schwarzkopf,
   Computational Geometry,
   Springer, 2000,
   ISBN: 3-540-65620-0,
   LC: QA448.D38.C65.
4. Qiang Du, Vance Faber, Max Gunzburger,
   Centroidal Voronoi Tessellations: Applications and Algorithms,
   SIAM Review,
   Volume 41, Number 4, December 1999, pages 637-676.
5. Herbert Edelsbrunner,
   Geometry and Topology for Mesh Generation,
   Cambridge, 2001,
   ISBN: 0-521-79309-2,
   LC: QA377.E36.
6. 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
7. 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.
8. 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.
9. Joseph ORourke,
   Computational Geometry,
   Second Edition,
   Cambridge, 1998,
   ISBN: 0521649765,
   LC: QA448.D38.
10. 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.
11. 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.

You can copy the source code for the slides:

• vt_2005.tex, the LaTeX source;
• ../../presentations/vt_2005.pdf, a PDF version;

The file includes various graphics files:

• cvt_movie_p08_0001.png, frame 1 of an animation of a CVT computation in the "holey pie" region. For the whole move, refer to CVT_MOVIE3.
• cvt_movie_p08_0100.png, frame 100 of an animation of a CVT computation in the "holey pie" region.
• cvt_movie2_0001.png, frame 1 of an animation of a CVT computation in a unit square. For the whole move, refer to CVT_MOVIE2.
• cvt_movie2_0100.png, frame 100 of an animation of a CVT computation in a unit square.
• cvt_movie4_0001.png, frame 1 of an animation of a CVT computation in a unit square with a nonuniform density that favors the corners. For the whole move, refer to CVT_MOVIE4.
• cvt_movie4_0100.png, frame 100 of an animation of a CVT computation in a unit square with a nonuniform density that favors the corners.
• diamond_02_00009_l2.png, a pixel plot of the Delaunay triangulation of the diamond points, generated by VORONOI_PLOT.
• diamond_02_00009_l3.png, a pixel plot of the Delaunay triangulation of the diamond points with the L3 distance, generated by VORONOI_PLOT.
• diamond_02_00009_li.png, a pixel plot of the Delaunay triangulation of the diamond points with the L-infinity distance, generated by VORONOI_PLOT.
• diamond_02_00009_l1.png, a pixel plot of the Delaunay triangulation of the diamond points with the L1 distance, generated by VORONOI_PLOT.
• diamond_02_00009_lhalf.png, a pixel plot of the Delaunay triangulation of the diamond points with the L(1/2) distance, generated by VORONOI_PLOT.
• diamond_delaunay.png, the Delaunay triangulation of the diamond points.
• diamond_delaunay_voronoi.png, the Delaunay triangulation and Voronoi diagram of the diamond points.
• 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_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.
• diamond_voronoi_matlab_1.png, MATLAB's default plot of the Voronoi diagram.
• diamond_voronoi_matlab_2.png, MATLAB's improved plot of the Voronoi diagram (using an unreleased version of the voronoi command).
• double_star.png, an image of a star in a star, with nodes and edges, generated by PLOT_TO_PS.
• fsu_logo_ybkgrd.pdf, an image of the FSU logo, with a yellow background.
• 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.
• 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.
• p05_nodes.png, a set of points to triangulate.
• p05_triangulation.png, the triangulated points.
• p14_boundary.png, the boundary of a lake, with an island.
• p14_dist.png, the distance-to-the-boundary calculation over the lake.
• p14_mesh.png, a uniform mesh over the lake, using Persson and Strang's DISTMESH program.
• p14_pred.png, the predator density in a time-dependent predator prey calculation, from work by Marcus Garvie.
• 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.
• square.png, an image of a square, with nodes and edges, generated by PLOT_TO_PS.
• stripack.png, plot of a Voronoi diagram on the surface of a sphere, generated by STRIPACK.
• tilapia.png, a photograph of tilapia nests in a sandy bottom, from the paper by Barlow.
• uniform_02_00100_km5.png, 100 random points clustered by K-Means into 5 groups.