Derandomizing an Output-Sensitive Convex Hull Algorithm in Three Dimensions

Abstract:

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
deterministic algorithm.

This technical report has been published as

Derandomizing an Output-Sensitive Convex Hull Algorithm in Three
Dimensions.
Bernard Chazelle and J. Matousek, Computational Geomtry: Theory and
Applications, 5, 1995, pp. 27-32.