The quickhull algorithm for convex hulls
- 1 December 1996
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Mathematical Software
- Vol. 22 (4) , 469-483
- https://doi.org/10.1145/235815.235821
Abstract
The convex hull of a set of points is the smallest convex set that contains the points. This article 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 used 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 serous 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.Keywords
This publication has 17 references indexed in Scilit:
- Closed-form solutions to constrained control allocation problemJournal of Guidance, Control, and Dynamics, 1995
- Four results on randomized incremental constructionsComputational Geometry, 1993
- On the randomized construction of the Delaunay treeTheoretical Computer Science, 1993
- Delaunay triangulations in three dimensions with finite precision arithmeticComputer Aided Geometric Design, 1992
- Voronoi diagrams—a survey of a fundamental geometric data structureACM Computing Surveys, 1991
- Applications of random sampling in computational geometry, IIDiscrete & Computational Geometry, 1989
- Voronoi diagrams from convex hullsInformation Processing Letters, 1979
- Convex hull of a finite set of points in two dimensionsInformation Processing Letters, 1978
- A New Convex Hull Algorithm for Planar SetsACM Transactions on Mathematical Software, 1977
- An Algorithm for Convex PolytopesJournal of the ACM, 1970