The quickhull algorithm for convex hulls
From MaRDI portal
Publication:4371114
DOI10.1145/235815.235821zbMath0884.65145OpenAlexW2153504150WikidataQ29014474 ScholiaQ29014474MaRDI QIDQ4371114
Hannu Huhdanpaa, David P. Dobkin, C. Bradford Barber
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/
algorithmconvex hullVoronoi diagramcomputational geometryDelaunay triangulationquickhull algorithmbeneath-beyond algorithm
Computational aspects related to convexity (52B55) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)
Related Items
Transient landing dynamics analysis for a lunar lander with random and interval fields, Robust vertex enumeration for convex hulls in high dimensions, Runtime monitors for Markov decision processes, Multi-periodic neural coding for adaptive information transfer, Gift-wrapping based preimage computation algorithm, An interdependency index for the outputs of uncertain systems, A homothetic reference technology in data envelopment analysis, Tetrahedral meshing via maximal Poisson-disk sampling, 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, A cutting plane algorithm for the capacitated facility location problem, Graphical exploration of the weight space in three-objective mixed integer linear programs, How good are convex hull algorithms?, Affine invariant comparison of point-sets using convex hulls and Hausdorff distances, Confinement-shear lattice CSL model for fracture propagation in concrete, Linearly interpolated FDH efficiency score for nonconvex frontiers, Computation of the best Diophantine approximations and of fundamental units of algebraic fields, Verified convex hull and distance computation for octree-encoded objects, Post-processing partitions to identify domains of modularity optimization, Coupling extended magnetohydrodynamic fluid codes with radiofrequency ray tracing codes for fusion modeling, Stochastic generation of particle structures with controlled degree of heterogeneity, Single particle fragmentation in ultrasound assisted impact comminution, Identifying connected components in Gaussian finite mixture models for clustering, Three-dimensional unstructured mesh generation. I: Fundamental aspects of triangulation and point creation, Multiscale modeling and characterization of granular matter: from grain kinematics to continuum mechanics, Extending local mixture models, Semi-explicit MPC based on subspace clustering, Post-optimality approach to prevent cycling in linear MPC target calculation, Numerical algorithm for solving the problem of synthesis of impulse controls under uncertainty, Analytic approximation of spatial epidemic models of foot and mouth disease, Computing projection depth and its associated estimators, Computing convex quadrangulations, Recursive voids for identifying a nonconvex boundary of a set of points in the plane, MPC of constrained discrete-time linear periodic systems -- a framework for asynchronous control: strong feasibility, stability and optimality via periodic invariance, Bivariate nonparametric estimation of the Pickands dependence function using Bernstein copula with kernel regression approach, An efficient convex hull algorithm using affine transformation in planar point set, Voronoi-cell finite difference method for accurate electronic structure calculation of polyatomic molecules on unstructured grids, Likelihood of environmental coalitions and the number of coalition members: evidences from an IAM model, Representation complexity of adaptive 3D distance fields, A local search algorithm for ray-convex polyhedron intersection, Dynamic balance preservation and prevention of sliding for humanoid robots in the presence of multiple spatial contacts, Computing multiple-output regression quantile regions, Principal components of sample estimates: an approach through symbolic data analysis, Statistical measures of two dimensional point set uniformity, Convex-hull algorithms: implementation, testing, and experimentation, Analysis of a triangulation based approach for specimen generation for discrete element simulations., Efficient mesh optimization schemes based on optimal Delaunay triangulations, Certifying algorithms, Knowledge-based computational mutagenesis for predicting the disease potential of human non-synonymous single nucleotide polymorphisms, Errors bounds for finite approximations of coherent lower previsions on finite probability spaces, Multivariate spacings based on data depth. I: Construction of nonparametric multivariate tolerance regions, Application of general semi-infinite programming to lapidary cutting problems, Methods for estimation of convex sets, Extended formulations for convex envelopes, Rock mechanics model capable of representing initial heterogeneities and full set of 3D failure mechanisms, Visualizing production surfaces in 3D diagrams, Interactive classification using data envelopment analysis, X-TMCMC: adaptive kriging for Bayesian inverse modeling, A general solution for robust linear programs with distortion risk constraints, The depth-design: an efficient generation of high dimensional computer experiments, Detecting kinematic boundary surfaces in phase space: particle mass measurements in SUSY-like events, Fuzzy clustering using the convex hull as geometrical model, Computing minimal interpolants in \(C^{1,1}(\mathbb{R}^d)\), Weighted sum model with partial preference information: application to multi-objective optimization, A parametric simplex algorithm for linear vector optimization problems, A simplicial homology algorithm for Lipschitz optimisation, A linear-time algorithm to compute the triangular hull of a digital object, PAINT: Pareto front interpolation for nonlinear multiobjective optimization, Computation for maximum stable grasping in dynamic force distribution, TRIOPT: A triangulation-based partitioning algorithm for global optimization, Real-time fuzzy regression analysis: a convex hull approach, Error control in polytope computations, Stochastic dynamic programming applied to hydrothermal power systems operation planning based on the convex hull algorithm, Convex hull properties and algorithms, Stability analysis of nonlinear quadratic systems via polyhedral Lyapunov functions, Surface area estimation of digitized 3D objects using quasi-Monte Carlo methods, Affine tensor product model transformation, Dynamic output feedback robust MPC with input saturation based on zonotopic set-membership estimation, Numerical methods for linear impulse feedback problems, A Matlab-based rapid method for computing lattice-subspaces and vector sublattices of \(\mathbb R^n\): applications in portfolio insurance, Convergent extension by intercalation without mediolaterally fixed cell motion, An empirical study of tests for uniformity in multidimensional data, Dynamic scheduling for switched processing systems with substantial service-mode switching times, A solution method for linear variational relation problems, Benson type algorithms for linear vector optimization and applications, Three-dimensional random Voronoi tessellations: from cubic crystal lattices to Poisson point processes, A multivariate uniformity test for the case of unknown support, Improved boundary tracking in meshless simulations of free-surface flows, A computational basis for higher-dimensional computational geometry and applications, Generalizations of Schöbi's tetrahedral dissection, A semi-supervised approach to space carving, Efficient \(O(N)\) integration for all-electron electronic structure calculation using numeric basis functions, Relaxation Runge-Kutta methods for Hamiltonian problems, Simplex based space filling designs, Carving out OPE space and precise O(2) model critical exponents, A fuzzy model for linear regression, Triangulations in CGAL, Optimal affine leader functions in reverse Stackelberg games. Existence conditions and characterization, Computing halfspace depth contours based on the idea of a circular sequence, A sausage heuristic for Steiner minimal trees in three-dimensional Euclidean space, Data-driven construction of convex region surrogate models, Exactly computing bivariate projection depth contours and median, \(N\)-body gravitational and contact dynamics for asteroid aggregation, 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, Guaranteed deterministic approach to superhedging: a numerical experiment, Counterexample-guided predicate abstraction of hybrid systems, Bayesian inversion using adaptive polynomial chaos kriging within subset simulation, Minimal enclosing parallelepiped in 3D, Almost-Delaunay simplices: Robust neighbor relations for imprecise 3D points using CGAL, Conservative interpolation of edge and face data on \(n\) dimensional structured grids using differential forms, Stable honeycomb structures and temperature based trajectory optimization for wire-arc additive manufacturing, An immersed boundary method for flows with dense particle suspensions, 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, Dissimilarity measures for population-based global optimization algorithms, A new active convex hull model for image regions, A convex hull approach for the reliability-based design optimization of nonlinear transient dynamic problems, Segmentation and analysis of neuroblastoma, Constrained random matching, Bounds on the complexity of halfspace intersections when the bounded faces have small dimension, Choosing among notions of multivariate depth statistics, On the resolution of certain discrete univariate max-min problems, Frequency estimate for multicomponent crystalline compounds, Algorithms and programs for calculating the roots of polynomial of one or two variables, Models of coral growth: spontaneous branching, compactification and the Laplacian growth assumption, Gibbs point field model quantifies disorder in microvasculature of U87-glioblastoma, A computational model of nuclear self-organisation in syncytial embryos, The NMF problem and lattice-subspaces, Machine learning based refinement strategies for polyhedral grids with applications to virtual element and polyhedral discontinuous Galerkin methods, A novel approach to generating microstructurally-aware non-convex domains, On ill-conceived initialization in archetypal analysis, Analytical enclosure of the set of solutions of the three-species multivariate curve resolution problem, On tail dependence matrices. The realization problem for parametric families, Influence of fracture gap size on the pattern of long bone healing: a computational study, Periodic three-dimensional mesh generation for particle reinforced composites with application to metal matrix composites, Observer-based output feedback robust MPC via zonotopic set-membership state estimation for LPV systems with bounded disturbances and noises, Efficient representation of Laguerre mosaics with an application to microstructure simulation of complex ore, Fast neighbor search by using revised \(k\)-d tree, Efficiently testing digital convexity and recognizing digital convex polygons, Normal form of a Hamiltonian system with a periodic perturbation, Algorithms for solving an algebraic equation, Computation of the fundamental units of number rings using a generalized continued fraction, Three-dimensional volume-conserving immersed boundary model for two-phase fluid flows, Quadrature schemes for arbitrary convex/concave volumes and integration of weak form in enriched partition of unity methods, On the energy-minimizing strains in martensitic microstructures. II: Geometrically linear theory, Delta Voronoi smoothed particle hydrodynamics, \(\delta\)-VSPH, A moment limiter for the discontinuous Galerkin method on unstructured tetrahedral meshes, A well-defined efficiency measure for dealing with closest targets in DEA, Computing traveltime and amplitude sensitivity kernels in finite-frequency tomography, Finding closest target for bank branches in the presence of weight restrictions using data envelopment analysis, Efficiency evaluation in data envelopment analysis using strong defining hyperplanes. A cross-efficiency framework, Determining closest targets on the extended facet production possibility set in data envelopment analysis: modeling and computational aspects, Analysis of landslides employing a space-time single-phase level-set method, Compensated convexity on bounded domains, mixed Moreau envelopes and computational methods, Primal-dual simplex method for multiobjective linear programming, A robust and scalable unfitted adaptive finite element framework for nonlinear solid mechanics, Computing equilibria in dynamic models with occasionally binding constraints, Mathematical modeling of ceramic bond bridges in grinding wheels, Classroom examples of robustness problems in geometric computations, From symmetry breaking to Poisson point process in 2D Voronoi tessellations: the generic nature of hexagons, An efficient algorithm to generate random sphere packs in arbitrary domains, A family of metrics for biopolymers based on counting independent sets, Evaluation of nondominated solution sets for \(k\)-objective optimization problems: an exact method and approximations, Density based fuzzy \(c\)-means clustering of non-convex patterns, Kernel interpolation, 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\), On exact Reznick, Hilbert-Artin and Putinar's representations, Iwasawa decomposition: a new approach to 2D affine registration problem, Color control of the multi-color printing device, XFEM-Based Fictitious Domain Method for Linear Elasticity Model with Crack, QuickhullDisk: a faster convex hull algorithm for disks, Multiparametric linear programming with applications to control, Computing multiple-output regression quantile regions from projection quantiles, A new variational approach based on level-set function for convex hull problem with outliers, Fast grid-free surface tracking, A linear-time approximate convex envelope algorithm using the double Legendre-Fenchel transform with application to phase separation, Estimating the number of stable configurations for the generalized Thomson problem, Approximation of virus structure by icosahedral tilings, LMI-based robust control of uncertain nonlinear systems via polytopes of polynomials, MCMC convergence diagnosis via multivariate bounds on log-concave densities, On the parametrization of an algebraic curve, CindyJS Plugins, Adaboost-based ensemble of polynomial chaos expansion with adaptive sampling, Identification and quantification of multivariate interval uncertainty in finite element models, Bayesian updating with subset simulation using artificial neural networks, Numerical Integration of Discontinuous Functions in Many Dimensions, A fictitious domain approach for a mixed finite element method solving the two-phase Stokes problem with surface tension forces, Two variations of graph test in double description method, A novel method based on similarity and triangulation for predicting the toxicities of various binary mixtures, Non-convex Pareto set navigation, Computational generation of open-foam representative volume elements with morphological control using distance fields, Fast multivariate log-concave density estimation, Grid generation and optimization based on centroidal Voronoi tessellations, A decomposition-based approach to layered manufacturing, Computing the integer hull of convex polyhedral sets, Robust optimization of attenuation bands of three-dimensional periodic frame structures, Parallel computing applied to the stochastic dynamic programming for long term operation planning of hydrothermal power systems, Testing over-representation of observations in subsets of a DEA technology, Algorithm 1024: Spherical Triangle Algorithm: A Fast Oracle for Convex Hull Membership Queries, Clustering of inertial particles in turbulent flow through a porous unit cell, FIXED GRID FINITE ELEMENT ANALYSIS FOR 3D STRUCTURAL PROBLEMS, A Bayesian regression approach to terrain mapping and an application to legged robot locomotion, Second-order comparison of three fundamental tessellation models, Convex Polyhedral Enclosures of Interval-Based Hierarchical Object Representations, A General Algorithm for Calculating Irreducible Brillouin Zones, Mixed Aggregated Finite Element Methods for the Unfitted Discretization of the Stokes Problem, On a scale-scale plot for comparing multivariate distributions, Fault-tolerant control design using the linear parameter varying approach, Unnamed Item, Efficient generation of densely packed convex polyhedra for 3D discrete and finite-discrete element methods, Non-differentiable saddle points and sub-optimal local minima exist for deep ReLU networks, The on-shell expansion: from Landau equations to the Newton polytope, Holistic fleet optimization incorporating system design considerations, Efficiency evaluation of very large-scale samples: data envelopment analysis with angle-index synthesis, Bayesian inference over ICA models: application to multibiometric score fusion with quality estimates, Simulation‐supported characterization of 3D‐printed biodegradable structures, Bounding the Kreuzer‐Skarke Landscape, A binary characterization method for shape convexity and applications, An envelope operator for full convexity to define polyhedral models in digital spaces, Extreme-value statistics from Lagrangian convex hull analysis for homogeneous turbulent Boussinesq convection and MHD convection, Incorporating working volume and projected area in design criteria for automotive SLA suspension, An extension to \textsc{Voro++} for multithreaded computation of Voronoi cells, A fast algorithm to solve large-scale matrix games based on dimensionality reduction and its application in multiple unmanned combat air vehicles attack-defense decision-making, Computing differential operators of the particle velocity in moving particle clouds using tessellations, Full convexity for polyhedral models in digital spaces, Mixed-integer programming techniques for the minimum sum-of-squares clustering problem, The projector algorithm: a simple parallel algorithm for computing Voronoi diagrams and Delaunay graphs, Determining the Number of Clusters Using Multivariate Ranks, Coupling pore network and finite element methods for rapid modelling of deformation, Stability and guaranteed error control of approximations to the Monge-Ampère equation, Simplex space–time meshes in finite element simulations, Soft theorem to three loops in QCD and \(\mathcal{N} = 4\) super Yang-Mills theory, Deriving robust noncontextuality inequalities from algebraic proofs of the Kochen–Specker theorem: the Peres–Mermin square, Minimal Volume Simplex (MVS) Polytopic Model Generation and Manipulation Methodology for TP Model Transformation, Recovering an electromagnetic obstacle by a few phaseless backscattering measurements, Bayesian alignment of proteins via Delaunay tetrahedralization, Divergence and convergence of inertial particles in high-Reynolds-number turbulence, Robust online Hamiltonian learning, Minkowski tensors of anisotropic spatial structure, Local Bisection for Conformal Refinement of Unstructured 4D Simplicial Meshes, The compressed differential heuristic, On feasible regions of lamination parameters for lay-up optimization of laminated composites, Robust fault detection based on adaptive threshold generation using interval LPV observers, On three-dimensional misorientation spaces, Workspace-Based Connectivity Oracle: An Adaptive Sampling Strategy for PRM Planning, Observed asymptotic differences in energies of stable and minimal point configurations on $\mathbb {S}^2$S2 and the role of defects, An algorithm to solve polyhedral convex set optimization problems, Computing Halfspace Depth and Regression Depth, k -d Darts, Stratifying High-Dimensional Data Based on Proximity to the Convex Hull Boundary, Indexing 3D Scenes Using the Interaction Bisector Surface, Failure of heterogeneous materials: 3D meso-scale FE models with embedded discontinuities, H ∞ ∕ H − LPV solutions for fault detection of aircraft actuator faults: Bridging the gap between theory and practice, Perfect lattices over imaginary quadratic number fields, Explicit polyhedral approximation of the Euclidean ball, On loop transformations of nested loops with affine dependencies, Increased mobility of bidisperse granular avalanches, Unnamed Item, Maximum Volume Inscribed Ellipsoid: A New Simplex-Structured Matrix Factorization Framework via Facet Enumeration and Convex Optimization, The natural element method in solid mechanics, An alternative definition for digital convexity, Efficient simulation of multi-body contact problems on complex geometries: A flexible decomposition approach using constrained minimization, An alternative definition for digital convexity, Mathematical model of an electromechanical actuator using flux state variables applied to reluctance motor, Structure-Specific Statistical Mapping of White Matter Tracts, Efficient Contact Mode Enumeration in 3D, Directional Distance Functions in DEA with Optimal Endogenous Directions, Fast Computation of Tukey Trimmed Regions and Median in Dimension p > 2, AN ALGORITHM FOR CALCULATING THE SET OF SUPERHEDGING PORTFOLIOS IN MARKETS WITH TRANSACTION COSTS, The inverse determination of aerodynamic loading from structural response data using neural networks, Multi-core Implementations of Geometric Algorithms, Interface handling for three-dimensional higher-order XFEM-computations in fluid-structure interaction, Self-Adaptive Density Estimation of Particle Data, Enforcing the non-negativity constraint and maximum principles for diffusion with decay on general computational grids, Euclidean Distance Matrix Completion and Point Configurations from the Minimal Spanning Tree, On uniform consistent estimators for convex regression, Efficient Algorithms to Test Digital Convexity, Passivity-preserving interpolation-based parameterized model order reduction of PEEC models based on scattered grids, Point-cloud method for image-based biomechanical stress analysis, An Adaptive Minimum Spanning Tree Multielement Method for Uncertainty Quantification of Smooth and Discontinuous Responses, A Lipschitz Matrix for Parameter Reduction in Computational Science, Integer hulls of linear polyhedra and scl in families, Unnamed Item, Local Graph Stability in Exponential Family Random Graph Models, Maximum Likelihood Estimation of a Multi-Dimensional Log-Concave Density, Numerical Approximation of the Value of a Stochastic Differential Game with Asymmetric Information, An experimental study of the stability problem in discrete tomography, TetGen, a Delaunay-Based Quality Tetrahedral Mesh Generator, Bayesian estimation of bivariate Pickands dependence function, The tightest knot is not necessarily the smallest, Optimal Sequential Multiclass Diagnosis
Uses Software
