600.488 Homework Assignment 6

All the problems of this homework assignment have to do with the farthest-point Voronoi diagram. Define the farthest-point Voronoi diagram as the union of farthest-point cells, where we define for each point p in a set S of n points the cell F(p) to be the set of all points that have p as their farthest neighbor in S.

1. Give an example of a set S and a point p in S such that F(p) is empty.
2. Show that each non-empty region in a farthest-point Voronoi diagram is unbounded and associated with a point on the convex hull of S.
3. Define the farthest-point Delaunay Triangulation as the graph-theoretic planar dual of the farthest-point Voronoi diagram. Derive a relationship between the farthest-point Delaunay Triangulation and the convex hull of the 3-dimensional set of points defined by mapping each point (x,y) in S to the point (x,y, x²+y²). Use this fact to design a simple O(n log n) time algorithm for constructing a fathest-point Voronoi diagram.
4. Prove that each vertex v of the farthest-point Voronoi diagram corresponds to a circle C determined uniquely by the sites defining v such that C contains all the points of S.
5. Show how to use the farthest-point Voronoi diagram to compute the smallest-radius circle that contains all the points of S. (Hint: the smallest one might be determined by only two points in S.) What is the running time of your method?