600.488 Homework Assignment 3
Due: Wednesday, February 24, 1999

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?

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?

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.

Prove by induction (not using the master theorem) that the running
time of the 2variable linear programming algorithm is
O(n).

Suppose you are given two convex polygons P and Q that
are separated by a vertical line, L.
Describe a lineartime algorithm for finding a line M that is
tangent to both P and Q and also intersects L.
Goodrich's Home Page.