The Quickhull Algorithm for Convex Hulls

Abstract:

The convex hull of a set of points is the smallest convex set that
contains the points. This paper presents a practical convex hull
algorithm that combines the two-dimensional Quickhull Algorithm with
the general dimension Beneath-Beyond Algorithm. It is similar to the
randomized, incremental algorithms for convex hull and Delaunay
triangulation. We provide empirical evidence that the algorithm runs
faster when the input contains nonextreme points, and that it uses
less memory.

Computational geometry algorithms have traditionally assumed that
input sets are well behaved. When an algorithm is implemented with
floating point arithmetic, this assumption can lead to serious
errors. We briefly describe a solution to this problem when computing
the convex hull in two, three, or four dimensions. The output is a set
of ``thick'' facets that contain all possible exact convex hulls of
the input. A variation is effective in five or more dimensions.

This technical report has been published as

The Quickhull Algorithm for Convex Hulls.
C. Bradford Barber, David P. Dobkin, and Hannu Huhdanpaa, ACM
Trans. on Math. Software, vol. 22, no. 4,
469-483, December 1996.

Here is the
software described in this paper and the tables for the paper
can be found in

BarberDobkinHuhdanpaa.tables.ps.Z, 11K.