600.488 Homework Assignment 5

Due: Wednesday, March 31, 1999

  1. Draw the Voronoi diagram of 10 points all on a line. Draw separately the Voronoi diagram of 10 points all on a circle. What do these two diagrams have in common?
  2. Draw the Voronoi diagram of 10 random points in the plane using the L-1 metric instead of the L-2 metric for defining inter-point distances. Show an example of a Voronoi cell that is not convex.
  3. Show that the closest pair of points p and q in a set of points in the plane have neighboring cells in this set's Voronoi diagram. That is, the Voronoi cell for p must share an edge with the Voronoi cell for q if they are the closest pair in the set.
  4. The set distance from a point p to a set of points S is defined as
    d(p,S) = min {d(p,q): q is in S},
    where d(a,b) is the normal Euclidean distance from a to b. The directed Hausdorf distance from a set of points A to a set of points B is
    H(A,B) = max {d(a,B): a is in A},
    and the Hausdorf distance between a set of points A and a set of points B is
    D(A,B) = max { H(A,B), H(B,A)}.
    This metric is used to measure similarity between two sets of points. Outline an efficient algorithm for computing the Hausdorf distance between two sets, A and B, each containing n points in the plane. What is the running time of your method?
  5. Suppose you are given a set S of n points in the plane and a rectangle R containing all these points in its interior. Describe an efficient algorithm for finding the largest circle that has its center inside R but contains none of the points of S in its interior (i.e., it is an empty circle). What is the running time of your method?