THE POISON PUMP AND THE SPITTING FISH

John Burkardt
School of Computational Scienc
Florida State University

26 April 2005

  In 1854, cholera broke out in a neighborhood of London.
While people didn't yet understand how diseases spread,
the pattern of this particular outbreak was so unusual it
seemed to have a message, though no one could read it.
Only the people in one area of town got sick; as time
passed, more people got sick here, but no where else.
All the people on a street would get sick, up to one
particular address, and beyond that, most people
were healthy.  It was only when a doctor drew the 
appropriate map of the district (and used the 
``walking-distance'' metric!) that an explanation appeared.

  In Africa, the mouthbreeder fish gather in sandy bottoms
of rivers to breed.  The females wander around, but the males 
tend to stay in one place, hollowing out a sort of pit in
the sand by taking a mouthful and spitting it away.  The
initially random configuration of male fish eventually takes
on a fairly regular pattern, with each fish in the center of
a roughly polygonal region.  

  These are two examples of the occurrence of Voronoi diagrams.
In this talk, we will also consider the dual concept of Delaunay 
triangulations, ways of computing these objects, whether
by hand or by computer.  We will also look at Monte Carlo techniques
for approximately computing Voronoi diagrams, which allows us to
work in higher dimensional spaces.  We will consider a special version
of the Voronoi diagram, in which the points are allowed to rearrange
themselves (like the African fish), resulting in a roughly hexagonal
grid.  We will consider applications in sampling, quadrature, and 
(non-uniform) mesh generation.