PRIMAL DIVIDING AND DUAL PRUNING - OUTPUT-SENSITIVE CONSTRUCTION OF 4-DIMENSIONAL POLYTOPES AND 3-DIMENSIONAL VORONOI DIAGRAMS

In this paper, we give an algorithm for output-sensitive construction of an f-face convex hull of a set of n points in general position 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 optim al O(n log f + f) time over the whole range of f. By a standard liftin g map, we obtain output-sensitive algorithms for the Voronoi diagram o r Delaunay triangulation in E-3 and for the portion of a Voronoi diagr am that is clipped to a convex polytope. Our approach simplifies the ' 'ultimate convex hull algorithm'' of Kirkpatrick and Seidel in E-2 and also leads to improved output-sensitive results on constructing conve x hulls in E-d for any even constant d > 4.