Published on *Computer Science Department at Princeton University* (http://www.cs.princeton.edu)

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,

Applications5, 1995, pp. 27-32.

**Links**

[1] http://www.cs.princeton.edu/research/techreps/author/283

[2] http://www.cs.princeton.edu/research/techreps/author/442

[3] ftp://ftp.cs.princeton.edu/techreports/1991/358.pdf