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)

• Numerical algorithm for solving the problem of synthesis of impulse controls under uncertainty
• Optimal affine leader functions in reverse Stackelberg games. Existence conditions and characterization
• Computing halfspace depth contours based on the idea of a circular sequence
• QuickhullDisk: a faster convex hull algorithm for disks
• Computing multiple-output regression quantile regions
• Numerical methods for linear impulse feedback problems
• Computing convex quadrangulations
• Minkowski tensors of anisotropic spatial structure
• Dissimilarity measures for population-based global optimization algorithms
• Robust fault detection based on adaptive threshold generation using interval LPV observers
• Second-order comparison of three fundamental tessellation models
• Models of coral growth: spontaneous branching, compactification and the Laplacian growth assumption
• Faster geometric algorithms via dynamic determinant computation
• Extending local mixture models
• Identifying connected components in Gaussian finite mixture models for clustering
• Analytic approximation of spatial epidemic models of foot and mouth disease
• Application of general semi-infinite programming to lapidary cutting problems
• A local search algorithm for ray-convex polyhedron intersection
• The natural element method in solid mechanics
• Multi-periodic neural coding for adaptive information transfer
• Statistical measures of two dimensional point set uniformity
• Enforcing the non-negativity constraint and maximum principles for diffusion with decay on general computational grids
• A Matlab-based rapid method for computing lattice-subspaces and vector sublattices of \(\mathbb R^n\): applications in portfolio insurance
• Efficient \(O(N)\) integration for all-electron electronic structure calculation using numeric basis functions
• A homothetic reference technology in data envelopment analysis
• An interdependency index for the outputs of uncertain systems
• Efficient generation of densely packed convex polyhedra for 3D discrete and finite-discrete element methods
• A convex hull approach for the reliability-based design optimization of nonlinear transient dynamic problems
• Triangulations in CGAL
• Surface area estimation of digitized 3D objects using quasi-Monte Carlo methods
• Local convex hulls for a special class of integer multicommodity flow problems
• Dynamic output feedback robust model predictive control via zonotopic set-membership estimation for constrained quasi-LPV systems
• Linearly interpolated FDH efficiency score for nonconvex frontiers
• A cutting plane algorithm for the capacitated facility location problem
• An algorithm for calculating the set of superhedging portfolios in markets with transaction costs
• Dynamic scheduling for switched processing systems with substantial service-mode switching times
• Extended formulations for convex envelopes
• Exactly computing bivariate projection depth contours and median
• Graphical exploration of the weight space in three-objective mixed integer linear programs
• Multivariate spacings based on data depth. I: Construction of nonparametric multivariate tolerance regions
• PAINT: Pareto front interpolation for nonlinear multiobjective optimization
• Computing multiple-output regression quantile regions from projection quantiles
• On feasible regions of lamination parameters for lay-up optimization of laminated composites
• Computation of the best Diophantine approximations and of fundamental units of algebraic fields
• Interface handling for three-dimensional higher-order XFEM-computations in fluid-structure interaction
• Robust online Hamiltonian learning
• Grid generation and optimization based on centroidal Voronoi tessellations
• Integer hulls of linear polyhedra and scl in families
• Directional distance functions in DEA with optimal endogenous directions
• Certifying algorithms
• Coupling extended magnetohydrodynamic fluid codes with radiofrequency ray tracing codes for fusion modeling
• Single particle fragmentation in ultrasound assisted impact comminution
• Stochastic generation of particle structures with controlled degree of heterogeneity
• Confinement-shear lattice CSL model for fracture propagation in concrete
• The Ultimate Planar Convex Hull Algorithm?
• Classroom examples of robustness problems in geometric computations
• A computational basis for higher-dimensional computational geometry and applications
• A solution method for linear variational relation problems
• Multiscale modeling and characterization of granular matter: from grain kinematics to continuum mechanics
• Identification and quantification of multivariate interval uncertainty in finite element models
• A Bayesian regression approach to terrain mapping and an application to legged robot locomotion
• Computation for maximum stable grasping in dynamic force distribution
• Quadrature schemes for arbitrary convex/concave volumes and integration of weak form in enriched partition of unity methods
• A well-defined efficiency measure for dealing with closest targets in DEA
• Multiparametric linear programming with applications to control
• Numerical integration of discontinuous functions in many dimensions
• Improved boundary tracking in meshless simulations of free-surface flows
• Maximum Likelihood Estimation of a Multi-Dimensional Log-Concave Density
• Benson type algorithms for linear vector optimization and applications
• Efficient simulation of multi-body contact problems on complex geometries: A flexible decomposition approach using constrained minimization
• Influence of fracture gap size on the pattern of long bone healing: a computational study
• TRIOPT: A triangulation-based partitioning algorithm for global optimization
• Knowledge-based computational mutagenesis for predicting the disease potential of human non-synonymous single nucleotide polymorphisms
• TetGen, a Delaunay-based quality tetrahedral mesh generator
• Failure of heterogeneous materials: 3D meso-scale FE models with embedded discontinuities
• A simplicial homology algorithm for Lipschitz optimisation
• Primal-dual simplex method for multiobjective linear programming
• Post-optimality approach to prevent cycling in linear MPC target calculation
• An algorithm to solve polyhedral convex set optimization problems
• Title not available (Why is that?)
• 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

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)