Making Quickhull More Like Quicksort: A Simple Randomized Output-Sensitive Convex Hull Algorithm

Michael T. Goodrich, Ryuto Kitagawa

In this paper, we present Ray-shooting Quickhull, which is a simple, randomized, outputsensitive version of the Quickhull algorithm for constructing the convex hull of a set of n p…