Randomizing an Output-Sensitive Convex Hull Algorithm in Three Dimensions
Report ID: TR-361-92Author: Chazelle, Bernard / Matousek, Jiri
Date: 1992-02-00
Pages: 6
Download Formats: |PDF|
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.