Primal Dividing and Dual Pruning: Output-Sensitive Construction of Four-Dimensional Polytopes and Three-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 ⁴. 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 ³ and for the portion of a Voronoi diagram that is clipped to a convex polytope. Our approach simplifies the ``ultimate convex hull algorithm'' of Kirkpatrick and Seidel in E ² and also leads to improved output-sensitive results on constructing convex hulls in E ^d for any even constant d > 4.

Authors and Affiliations

1. Department of Computer Science, University of British Columbia, Vancouver, BC, Canada V6T 1Z4, , , , , , CA

   T. M. Chan & J. Snoeyink

2. Courant Institute of Mathematical Sciences, New York University, New York, NY 10012, USA, , , , , , US

   Chee-Keng Yap

Received August 3, 1995, and in revised form September 19, 1996.

Reprints and permissions