Given a set S of points in the plane, define the Delaunay triangulation of S to be the set of all triangles (p, q, r) such that p, q, and r are in S and the circle defined to have these points on its boundary is empty—it contains no points of S in its interior. Such triangulations have many applications to modeling problems, as Delaunay triangulations tend to avoid “long and skinny” triangles, which are bad for modeling applications. 

a. Show that if p and q are a closest pair of points in the set S, then p and q are joined by an edge in the Delaunay triangulation. 

b. Show that the Voronoi cells V (p) and V (q), as defined in the previous exercise, share an edge in the Voronoi diagram of a point set S if and only if p and q are joined by an edge in the Delaunay triangulation of S.