600.488 Homework Assignment 4

Due: Wednesday, April 8, 1998

  1. 20 points. Suppose you are given two disjoint convex polyhedra P and Q in 3-dimensional space. Recall that 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. In class I showed that the trace of the sleeve on P need not be simple, and can be topologically equivalent to a ``bar bell.'' 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

  2. 20 points. Let P be a 3-dimensional convex polyhedron with n vertices, stored in your favorite 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.)
  3. 20 points. Let A and be a set of n points in the plane. Develop an efficient algorithm to find the largest empty circle whose center is inside the convex hull of A. What is the running time of your algorithm?
  4. 20 points. Given a convex polyhedron P in three dimensional space, develop an efficient data structure for answering vector-normal queries. In a vector-normal query one is given a vector v and asked to identify the face, edge, or vertex on P that has v as (one of) its outward-pointing normal(s). Shoot for a query time of O(log n). What is the space complexity and preprocessing time of your data structure?
  5. 20 points. Suppose you are given only the Delaunay triangulation of a set S of n point in the plane. Describe the details for constructing the Voronoi diagram of S from this Delaunay triangulation in O(n) time.