600.488 Homework Assignment 4

Due: Wednesday, March 3, 1999

  1. 20 points. Suppose you are given a set S of n points in the plane. Define the width of S to be the smallest distance between two parallel lines L and M such that all the points of S are between L and M (or on one of these lines). Describe an efficient data structure for determining the width of S. What is the running time of your method?
  2. 20 points. Suppose you are given two disjoint convex polyhedra P and Q in 3-dimensional space. The sleeve of P and Q is defined to be the set of triangular faces of the convex hull of the union of P and Q that do not already appear on either P or Q. Define the trace of the sleeve on P to be the intersection of the sleeve with P, which defines a piece-wise linear curve. Counter to intuition, the trace of the sleeve on P need not be simple. Construct a physical model (out of paper, cardboard, coat hangers, clay, ...) to show that the trace of the sleeve on P can be topologically equivalent to a 3-armed ``windmill'', as drawn below:

    Three triangles joined to a single vertex by three edges

  3. 10 points. Let P be a 3-dimensional convex polyhedron with n vertices, stored in your favorite subdivision data structure. Describe how to compute the shadow of P, given a light source at infinity in direction v. (The shadow is the polygon that is the projection of P onto a plane perpendicular to v.)

    Goodrich's Home Page.