ABSTRACT:
 In this paper, we give an algorithm for output-sensitive construction
of an $f$-face polytope that is defined by $n$ halfspaces in $E^4$.
Our algorithm runs in \O{(n+f){\log^2 f}} time and uses \O{n+f} space.
This is the first algorithm within a polylogarithmic factor of optimal
\O{n\log f + f} time over the whole range of $f$.  By a standard
lifting map, we obtain output-sensitive algorithms for the Voronoi
diagram or Delaunay triangulation in $E^3$ and for the portion of a
Voronoi diagram that is clipped to a convex polytope.  Our approach
also simplifies the ``ultimate convex hull algorithm'' of Kirkpatrick
and Seidel in $E^2$.