600.488 Homework Assignment 3

Due: Wednesday, April 1, 1998

  1. 20 pts. A line segment in the plane is isothetic if it is parallel to either the x- or y-axis, and a rectangle is isothetic if all of its boundary line segments are isothetic. Design efficient algorithms for each of the following problems:
    1. Rectilinear Segment Intersection Counting. Given n horizontal and vertical line segments in the plane, determine for each segment s the number of other segements which intersect s.
    2. Rectangle Searching: Counting Problem. Given n isothetic rectangles in the plane and n points in the plane determine for each point p the number of rectangles which contain p in their interior.
  2. 20 points. Design an efficient algorithm to solve the following problem: Given n ``mouse'' robots and n ``cheese'' spots, whose respective positions are specificed by points in the plane, such that the mouse robots are separated from the cheese spots by a vertical line, find a matching of the mice points with the cheese points by straight line segments so that every mouse point is matched with a cheese point and such that no two segments intersect. Intuitively, this corresponds to the paths the mice will have to make so that each mouse can get to a piece of cheese without crashing into any other mouse.
  3. 20 points. Describe an efficient way to implement the following procedure:
    1. Set i to 1.
    2. Find the convex hull, H, of S.
    3. Mark each point in H as being on ``layer'' i.
    4. Remove each point in H from S.
    5. Set i to i+1.
    6. If S is not empty, then goto Step 2.
  4. 20 points. The layers defined by the above procedure produce an ``onion'' of nested convex polygons. Describe a data structure to quickly determine the layer number that a query point p would have if it were added to S and we were to re-run the above procedure. Shoot for a query time of O(log n) and space/pre-processing of O(n), given the convex layers of S.
  5. 20 points. 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.