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

Report ID:

TR-565-95

Authors:

Date:

December 1994

Pages:

15

Download Formats:

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, vol. 22, no. 4,

Trans. on Math. Software

469-483, December 1996.- Here is the

software described in this paper and the tables for the paper

can be found inBarberDobkinHuhdanpaa.tables.ps.Z, 11K.