In this chapter we study the Voronoi diagram, a geometric structure second in importance only to the convex hull. In a sense a Voronoi diagram records everything one would ever want to know about proximity to a set of points (or more general objects). And often one does want to know detail about proximity: Who is closest to whom? who is furthest? and so on. The concept is more than a century old, discussed in 1850 by Dirichlet and in a 1908 paper of Voronoi.1
We will start with a series of examples to motivate the discussion ...