600.488 Homework Assignment 4

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?
 
Solution: We assume the convex hull  H of the set of points is known.  This corresponds
to a preprocessing time equal to O(nlog(n)).  The storage space is O(n), since we are
just storing points.  We assume that this convex hull is stored on a balanced binary
search tree, thus achieving O(log(n)) for binary searches and also fast updates in case
S, and consequently H, are changed.

Now for the algorithm itself.  Each vertex of the null defines a certain interval of slopes
corresponding to those lines supporting the hull at the vertex.  A vertex is completely
characterized by indicating the range of supporting slopes plus whether it belongs to
the upper or lower hull. (These slopes also correspond to the turning angle at that vertex.
Since turning angles add up to 360, for each slope theta there are supporting lines with
slope tan(theta)  at exactly two vertices, one belonging to the lower and other to the upper
hull.)

By travelling along the upper hull and measuring the turning angles, we can in O(n) time
determine a "upper" partition of the interval [0, Pi] into n regions that correspond each
to the particular range of supporting angles of a  vertex in the upper hull.  We
simultaneously define a superimposed "lower" partition corresponding to the vertices in
the lower hull.  We have thus subdivided the interval in at most 2n parts, each of
which defines a candidate pair of vertices to determine the width of the set.  We can now
exhaust the possibilites by trying any possible pair.  This will take O(n) time.

A few details:  To find the width at one of the "candidate pairs" above, pass a line l
connecting the two points and compute among the slopes available for the pair
(the values contained in the particular subinterval of the subdivision of [0, Pi] that
correspond to this pair) the one which will give a supporting line that is as far as possible
from being orthogonal to l.  The distance between these two parallel supporting lines
is thus the projection of  l on the orthogonal direction to the lines, and was thus minimized
for the pair.  These computations take constant time at each pair.

The correctness of the algorithm is guaranteed by the fact that it exhausts every pair that
may share parallel supporting lines.  It does queries in linear as opposed to
quadratic time because our analysis of the turning angles shows that there are only
O(n) pairs of opposing vertices in a convex polygon, and determines these possible
pairs in linear time.
 

 


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.)

Without loss of generality, we may assume the source is at infinity along the direction
of the z-axis. The vertex of  P  with maximum x-coordinate will thus project its shadow
on the xy-plane.   Call this vertex v.  Starting from v we procceed to perform a
two-dimensional gift wrapping step (that is, we use the z-axis as hinge) to find the
first edge from v.  Notice that since  P is known, the gift wrapping process runs in time
O(d(v)), where d(v) is the number of edges incident on v. We continue from the vertex
at the other end of the this edge, and we will finish when we return back to v.   The
shadow of P is thus the interior and boundary of the convex polygon traced on the
xy-plane by the projections of the edges found in the gift wrapping process.

The algorithm searches for a point with maximum x-coordinate, which in general could
take time proportional to the number of vertices of P, and then performs one gift
wrapping step for each vertex of P that contributes to the shadow.  The running time,
is O(n(P) + sum(d(v_i)) ), where the v_i are the vertices of P projecting shadow.