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 (only showing first 100 items - show all)
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
Uses Software
This page was built for publication: The quickhull algorithm for convex hulls
