600.488 Homework Assignment 4
Due: Wednesday, March 3, 1999

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?

20 points.
Suppose you are given two
disjoint convex polyhedra P and Q in 3dimensional
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 piecewise 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 3armed ``windmill'', as drawn below:

10 points.
Let P be a 3dimensional
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.