The quickhull algorithm for convex hulls

By C. Barber, David P. Dobkin, H. Huhdanpaa. 1996

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Algorithms & Complexity

Citations in the corpus

Robust Classification for Imprecise Environments (2000, methodology): “Finally, the time eﬃciency of the rocch -hybrid depends on the eﬃciency of building the rocch , which can be done in O ( N log N ) time using the QuickHull algorithm (Barber et al., 1996) where N is the number of classiﬁers.”
Graspit! A versatile simulator for robotic grasping (2004, methodology): “These six-dimensional (6-D), convex hull operations are performed quickly using the qhull library [20].”
Periodic three-dimensional mesh generation for crystalline aggregates based on Voronoi tessellations (2009, methodology): “The computation of the Voronoi tessellation itself is carried out by using the QHull package [ 7 ] which is fast and robust.”
Tree species classification and estimation of stem volume and DBH based on single tree extraction by exploiting airborne full-waveform LiDAR data (2012, methodology): “Additionally, we estimate for each segmented tree i the tree area Acrown by calculating the maximal 2D convex hull of the crown points (Barber et al., 1996).”
Computing structure-based lipid accessibility of membrane proteins with mp_lipid_acc in RosettaMP (2016, methodology): “The convex hull is the smallest set of points on the outer perimeter of the 2D point cloud that encloses the entire point cloud; it is computed by a QuickHull algorithm [31, 32] (see below).”
LIME - a flexible, non-LTE line excitation and radiation transfer method for millimeter and far-infrared wavelengths (2010, methodology): “When the point distribution has been obtained, the points are connected by Delaunay triangulation, using the public available QHull library (Barber et al. 1996).”
A convex hull approach for the reliability-based design optimization of nonlinear transient dynamic problems (2007, background): “It is to be noted that a convex hull is not limited to two dimensions and can be easily extended to several dimensions (Barber et al., 1996).”
A trait-based test for habitat filtering: convex hull volume. (2006, background): “…could be used to enclose the points (e.g., the smallest cube or sphere), the convex hull, defined as the smallest convex set enclosing the points (Preparata and Shamos 1985, Barber et al. 1996), is the most reasonable as it reduces the amount of empty space compared to cubes or spheres (see Fig.”