The quickhull algorithm for convex hulls

DOI10.1145/235815.235821zbMATH Open0884.65145OpenAlexW2153504150WikidataQ29014474 ScholiaQ29014474MaRDI QIDQ4371114FDOQ4371114

Authors: C. Bradford Barber, David P. Dobkin, Hannu Huhdanpaa 

Publication date: 7 January 1998

Published in: ACM Transactions on Mathematical Software (Search for Journal in Brave)

Full work available at URL: http://www.acm.org/pubs/contents/journals/toms/1996-22/

Recommendations

• An efficient and numerically correct algorithm for the 2D convex hull problem
• EXACT AND OPTIMAL CONVEX HULLS IN 2D
• Quicker than Quickhull
• scientific article; zbMATH DE number 724218
• Computing convex hull in a floating point arithmetic

zbMATH Keywords

algorithmcomputational geometryconvex hullDelaunay triangulationVoronoi diagramquickhull algorithmbeneath-beyond algorithm

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Cited In (only showing first 100 items - show all)

• Analysis of landslides employing a space-time single-phase level-set method
• A direct method for determining the lower convex hull of a finite point set in 3D
• Divergence and convergence of inertial particles in high-Reynolds-number turbulence
• Computation of the fundamental units of number rings using a generalized continued fraction
• Efficiency evaluation in data envelopment analysis using strong defining hyperplanes. A cross-efficiency framework
• On three-dimensional misorientation spaces
• Delta Voronoi smoothed particle hydrodynamics, \(\delta\)-VSPH
• Bayesian updating with subset simulation using artificial neural networks
• Mathematical modeling of ceramic bond bridges in grinding wheels
• Structure-Specific Statistical Mapping of White Matter Tracts
• Robust optimization of attenuation bands of three-dimensional periodic frame structures
• Fault-tolerant control design using the linear parameter varying approach
• \(k\)-d darts, sampling by \(k\)-dimensional flat searches
• An efficient algorithm to generate random sphere packs in arbitrary domains
• A fast algorithm to decide the inclusion of a point in the convex hull of a two-dimensional point set
• Minimal enclosing parallelepiped in 3D
• XFEM-based fictitious domain method for linear elasticity model with crack
• Finding closest target for bank branches in the presence of weight restrictions using data envelopment analysis
• Detection and computation of conservative kernels of models consisting of freeform curves and surfaces, using inequality constraints
• Mesh generation for periodic 3D microstructure models and computation of effective properties
• Compensated convexity on bounded domains, mixed Moreau envelopes and computational methods
• Guaranteed deterministic approach to superhedging: a numerical experiment
• A fictitious domain approach for a mixed finite element method solving the two-phase Stokes problem with surface tension forces
• Efficient Algorithms to Test Digital Convexity
• The inverse determination of aerodynamic loading from structural response data using neural networks
• Efficiently testing digital convexity and recognizing digital convex polygons
• Stable honeycomb structures and temperature based trajectory optimization for wire-arc additive manufacturing
• Employing the MCMC technique to compute the projection depth in high dimensions
• An efficient and robust GPGPU-parallelized contact algorithm for the combined finite-discrete element method
• A moment limiter for the discontinuous Galerkin method on unstructured tetrahedral meshes
• On exact Reznick, Hilbert-Artin and Putinar's representations
• Segmentation and analysis of neuroblastoma
• Normal form of a Hamiltonian system with a periodic perturbation
• A new variational approach based on level-set function for convex hull problem with outliers
• On tail dependence matrices. The realization problem for parametric families
• Algorithms and programs for calculating the roots of polynomial of one or two variables
• Constrained random matching
• Mixed Aggregated Finite Element Methods for the Unfitted Discretization of the Stokes Problem
• Evaluation of nondominated solution sets for \(k\)-objective optimization problems: an exact method and approximations
• Bayesian inversion using adaptive polynomial chaos kriging within subset simulation
• Choosing among notions of multivariate depth statistics
• Estimating the number of stable configurations for the generalized Thomson problem
• Complexity of methods for approximating convex compact bodies by double description polytopes and complexity bounds for a hyperball
• A filtering technique for fast convex hull construction in \(\mathbb{R}^2\)
• Iwasawa decomposition: a new approach to 2D affine registration problem
• Bounding the Kreuzer‐Skarke Landscape
• Local Bisection for Conformal Refinement of Unstructured 4D Simplicial Meshes
• Adaboost-based ensemble of polynomial chaos expansion with adaptive sampling
• Stratifying high-dimensional data based on proximity to the convex hull boundary
• Observer-based output feedback robust MPC via zonotopic set-membership state estimation for LPV systems with bounded disturbances and noises
• Gibbs point field model quantifies disorder in microvasculature of U87-glioblastoma
• Determining closest targets on the extended facet production possibility set in data envelopment analysis: modeling and computational aspects
• Algorithm 1024: Spherical Triangle Algorithm: A Fast Oracle for Convex Hull Membership Queries
• The NMF problem and lattice-subspaces
• A novel approach to generating microstructurally-aware non-convex domains
• Efficient representation of Laguerre mosaics with an application to microstructure simulation of complex ore
• Non-convex Pareto set navigation
• Bounds on the complexity of halfspace intersections when the bounded faces have small dimension
• From Diophantine approximations to Diophantine equations
• Deriving robust noncontextuality inequalities from algebraic proofs of the Kochen–Specker theorem: the Peres–Mermin square
• Transient landing dynamics analysis for a lunar lander with random and interval fields
• On uniform consistent estimators for convex regression
• A sublogarithmic convex hull algorithm
• Detecting kinematic boundary surfaces in phase space: particle mass measurements in SUSY-like events
• Affine invariant comparison of point-sets using convex hulls and Hausdorff distances
• Robust vertex enumeration for convex hulls in high dimensions
• Runtime monitors for Markov decision processes
• Gift-wrapping based preimage computation algorithm
• Density based fuzzy \(c\)-means clustering of non-convex patterns
• Computing halfspace depth and regression depth
• Determining the number of clusters using multivariate ranks
• Periodic three-dimensional mesh generation for particle reinforced composites with application to metal matrix composites
• Error control in polytope computations
• Robust gift wrapping for the three-dimensional convex hull
• Three-dimensional volume-conserving immersed boundary model for two-phase fluid flows
• Almost-Delaunay simplices: Robust neighbor relations for imprecise 3D points using CGAL
• Real-time fuzzy regression analysis: a convex hull approach
• Methods for estimation of convex sets
• Fast neighbor search by using revised \(k\)-d tree
• A fast and efficient algorithm for determining the connected orthogonal convex hulls
• An adaptive minimum spanning tree multielement method for uncertainty quantification of smooth and discontinuous responses
• Stability analysis of nonlinear quadratic systems via polyhedral Lyapunov functions
• An efficient convex hull algorithm using affine transformation in planar point set
• On the energy-minimizing strains in martensitic microstructures. II: Geometrically linear theory
• Fast multivariate log-concave density estimation
• Fast Computation of Tukey Trimmed Regions and Median in Dimension p > 2
• Computing the integer hull of convex polyhedral sets
• Recovering an electromagnetic obstacle by a few phaseless backscattering measurements
• Counterexample-guided predicate abstraction of hybrid systems
• Parallel computing applied to the stochastic dynamic programming for long term operation planning of hydrothermal power systems
• A CONVEX HULL ALGORITHM FOR POINTS WITH APPROXIMATELY KNOWN POSITIONS
• Bayesian alignment of proteins via Delaunay tetrahedralization
• A multivariate uniformity test for the case of unknown support
• Kernel interpolation
• Observed asymptotic differences in energies of stable and minimal point configurations on \(\mathbb{S}^2\) and the role of defects
• A fuzzy model for linear regression
• Voronoi-cell finite difference method for accurate electronic structure calculation of polyatomic molecules on unstructured grids
• Representation complexity of adaptive 3D distance fields
• A sausage heuristic for Steiner minimal trees in three-dimensional Euclidean space
• A robust and scalable unfitted adaptive finite element framework for nonlinear solid mechanics

Uses Software

• Qhull
• Triangle
• DIMACS
• Hull

This page was built for publication: The quickhull algorithm for convex hulls

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4371114)