A FEW YEARS AGO some students and I were looking at a map that pinpointed the
locations of about loo cities. We asked ourselves, "Which of these cities are neighbors
of each other?" We knew intuitively that some pairs of cities were neighbors and others
were not; we wanted to find a formal mathematical characterization that would match
our intuition.
Our first solution was rather complicated. We decided to say that points p and q
of a given set S are neighbors if the set V of all points in the plane that are closer to p
than to any other point of S is adjacent to the set Vq of all points that are closest to q.
Another way to state this condition is so say that V and Vq have a common boundary
point t; point t is then equidistant from p and q, and every point between p and t
belongs to V, while every point between q and t belongs to Vq. After several more
minutes we realized that the key fact was the existence of a circle running through
points p and q (centered at t), with no points of S inside the circle.
We began to look for an algorithm that would find all neighboring pairs of points
{p, q}, according to our criterion. But time ran out; our meeting had to break up, and
we went our separate ways. I wonder what would have happened if we had had more
time to explore the problem on our own, before learning that it was a famous problem
in computational geometry.
Leo Guibas's office was next to mine, and we soon learned from him that points
p and q are neighbors in S by our definition if and only if the line segment pq belongs
to the so-called Delaunay triangulation of S. I had never encountered that branch of
geometry before, and I hadn't had time to read much of the fast-growing literature of
computational geometry. After all, I had never promised to write a book about such
things, and the other topics that had kept me going for 30 years were already proving
to be more than adequate to occupy an entire lifetime! Furthermore I knew that my
geometric intuition was rather poor; algebra and logic have always been much easier
for me than visualization. I have absolutely no ability to understand 3-dimensional
objects until I have built physical models to represent them.
Leo gave me a reprint of [38], a paper that explains (among other things) how
to compute the Delaunay triangulation of n points in O(n log n) steps, using simple
primitive operations and elegant data structures. I knew I didn't have time to
read it, but I was immediately fascinated. Here was the clarity I was looking for, a
paper that provided a bridge between algebraic and geometric intuition. I still had
difficulty, however, understanding some of the proofs, which relied on diagrams that
illustrated particular cases. I craved a proof of the algorithm that could be checked
by a computer.
So I spent a