600.488 Homework Assignment 4
Due: Wednesday, March 3, 1999
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
Describe an efficient data structure for determining the width of
What is the running time of your method?
Suppose you are given two
disjoint convex polyhedra P and Q in 3-dimensional
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
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:
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.