The Quickhull Algorithm for Convex Hulls

The Quickhull Algorithm for Convex Hulls

December 1996 | C. BRADFORD BARBER, DAVID P. DOBKIN, HANNU HUHDANPAA
The article presents the Quickhull Algorithm, a practical method for computing the convex hull of a set of points in any dimension. The algorithm combines the two-dimensional Quickhull Algorithm with the general-dimension Beneath-Beyond Algorithm, similar to randomized and incremental algorithms for convex hulls and Delaunay triangulation. The authors provide empirical evidence that Quickhull runs faster when the input contains nonextreme points and uses less memory. They also describe a solution to handle floating-point arithmetic errors, which can lead to degeneracies in the convex hull computation. The Quickhull Algorithm is implemented and available as the qhull program, which can compute convex hulls, Delaunay triangulations, Voronoi vertices, and halfspace intersections. The program includes options for imprecise data, facet area, hull volume, and graphical output. The authors have used Quickhull in various applications, including layered manufacturing, molecular classification, and robot navigation.The article presents the Quickhull Algorithm, a practical method for computing the convex hull of a set of points in any dimension. The algorithm combines the two-dimensional Quickhull Algorithm with the general-dimension Beneath-Beyond Algorithm, similar to randomized and incremental algorithms for convex hulls and Delaunay triangulation. The authors provide empirical evidence that Quickhull runs faster when the input contains nonextreme points and uses less memory. They also describe a solution to handle floating-point arithmetic errors, which can lead to degeneracies in the convex hull computation. The Quickhull Algorithm is implemented and available as the qhull program, which can compute convex hulls, Delaunay triangulations, Voronoi vertices, and halfspace intersections. The program includes options for imprecise data, facet area, hull volume, and graphical output. The authors have used Quickhull in various applications, including layered manufacturing, molecular classification, and robot navigation.
Reach us at info@study.space
[slides] The quickhull algorithm for convex hulls | StudySpace