CIS 677: Homework 3, due about Nov. 3

1. In Lecture 6, some relations were claimed about the edge sets of some geometric graphs:

   RNG(S) subset GG(S) subset DG(S).

   Prove these relations. Given efficient algorithms to compute RNG(S) and GG(S). (See problems 9.8 and 9.9 of the text for a hint.)
2. Problem 7.10 of the text: Let P be a set of n points in the plane. Give an O(n log n) algorithm to find two points in P that are closest together. Show that your algorithm is correct.
3. Problem 7.11 of the text: Let P be a set of n points in the plane. Given an O(n log n) time algorithm to find for each point p in P another point in P that is closest to it.
4. Problem 9.3 of the text.
5. Use the farthest point Voronoi diagram to show that the smallest circle enclosing a set of points can be found in O(n log n) time.
6. The discrete 1-center of a set of points S is the member of S whose maximum distance to the remaining points of S is smallest, over all points of points of S. That is, cent(S) gives

   min_{p in S} max_{q in S-{p}} d(p,q).

   Show that the discrete 1-center of S can be found in O(n log n) time.