600.488 Homework Assignment 3

Due: Wednesday, February 24, 1999

  1. Suppose you are given a collection S of n line segments in the plane, each of which is either vertical or horizontal. Design an efficient algorithm for counting the number of pairwise intersections between the segments in S. What is the running time of your method?
  2. Suppose you are given a collection S of n points in the plane, one of which is marked as "special." Design an efficient algorithm for determining if the special point can be separated from the rest of the points in S by a line, with the special point on one side and the rest of the points on the other. What is the running time of your method?
  3. Suppose you are given a simple polygon P that has been triangulated. Suppose further that you are given two points p and q inside P. Describe an efficient algorithm to list (in order) all the triangles that would have to be crossed by a shortest path from p to q that is constrained to stay in the interior of P.
  4. Prove by induction (not using the master theorem) that the running time of the 2-variable linear programming algorithm is O(n).
  5. Suppose you are given two convex polygons P and Q that are separated by a vertical line, L. Describe a linear-time algorithm for finding a line M that is tangent to both P and Q and also intersects L.


Goodrich's Home Page.