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.