600.488 Homework Assignment 4
Due: Wednesday, April 8, 1998
Suppose you are given two
disjoint convex polyhedra P and Q in 3-dimensional
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
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:
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.)
Let A and be a set of n points in the
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?
Given a convex polyhedron P in three dimensional space,
develop an efficient data structure for answering vector-normal
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?
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.