Randomizing 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 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.