Derandomizing an Output-Sensitive Convex Hull Algorithm in Three Dimensions
We consider the computation of the convex hull of a given $n$-point set
in three-dimensional Euclidean space in an output-sensitive manner.
Clarkson and Shor proposed an optimal randomized algorithm for this
problem, with an expected running time of $O(n^log^h)$, where $h$
denotes the number of points on the surface of the convex hull. In
this note we point out that the algorithm can be made deterministic by
using recently developed techniques, thus obtaining an optimal
- This technical report has been published as
- Derandomizing an Output-Sensitive Convex Hull Algorithm in Three
Bernard Chazelle and J. Matousek, Computational Geomtry: Theory and
Applications, 5, 1995, pp. 27-32.