ISSN:
1432-0444
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract. 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 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 simplifies the ``ultimate convex hull algorithm'' of Kirkpatrick and Seidel in E 2 and also leads to improved output-sensitive results on constructing convex hulls in E d for any even constant d 〉 4.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/PL00009327
