How good are convex hull algorithms?
From MaRDI portal
Publication:1356937
DOI10.1016/S0925-7721(96)00023-5zbMath0877.68119WikidataQ29542125 ScholiaQ29542125MaRDI QIDQ1356937
David Avis, Raimund Seidel, David Bremner
Publication date: 8 December 1997
Published in: Computational Geometry (Search for Journal in Brave)
Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)
Related Items (57)
A linear optimization oracle for zonotope computation ⋮ Dealing with imprecise information in group multicriteria decisions: a methodology and a GDSS architecture ⋮ Enumeration of Nash equilibria for two-player games ⋮ The \(d\)-majorization polytope ⋮ Convex hulls, oracles, and homology ⋮ Constrained random matching ⋮ Bounds on the complexity of halfspace intersections when the bounded faces have small dimension ⋮ Computing convex hulls and counting integer points with \texttt{polymake} ⋮ Sum-of-squares methods for controlled invariant sets with applications to model-predictive control ⋮ On a cone covering problem ⋮ Packing convex polygons in minimum-perimeter convex hulls ⋮ Nonlinear set membership filter with state estimation constraints via consensus-ADMM ⋮ Partial identification in nonseparable binary response models with endogenous regressors ⋮ Deriving robust noncontextuality inequalities from algebraic proofs of the Kochen–Specker theorem: the Peres–Mermin square ⋮ Convex hulls of spheres and convex hulls of disjoint convex polytopes ⋮ A tree traversal algorithm for decision problems in knot theory and 3-manifold topology ⋮ a-tint: a polymake extension for algorithmic tropical intersection theory ⋮ The negative cycles polyhedron and hardness of checking some polyhedral properties ⋮ Computational tools for solving a marginal problem with applications in Bell non-locality and causal modeling ⋮ Linear inequalities among graph invariants: Using GraPHedron to uncover optimal relationships ⋮ Efficient edge-skeleton computation for polytopes defined by oracles ⋮ Facet defining inequalities among graph invariants: The system graphedron ⋮ An efficient local approach to convexity testing of piecewise-linear hypersurfaces ⋮ Identification of unidentified equality constraints for integer programming problems ⋮ On the hardness of computing intersection, union and Minkowski sum of polytopes ⋮ Globally tight bounds for almost differentiable functions over polytopes with application to tolerance analysis. ⋮ A linear-time algorithm to compute the triangular hull of a digital object ⋮ Optimizing the double description method for normal surface enumeration ⋮ A complete description of cones and polytopes including hypervolumes of all facets of a polytope ⋮ Self-duality of polytopes and its relations to vertex enumeration and graph isomorphism ⋮ PALP: a package for analysing lattice polytopes with applications to toric geometry ⋮ A validation and verification tool for global optimization solvers ⋮ DECOMPOSITION AND PARALLELIZATION TECHNIQUES FOR ENUMERATING THE FACETS OF COMBINATORIAL POLYTOPES ⋮ Complexity of methods for approximating convex compact bodies by double description polytopes and complexity bounds for a hyperball ⋮ Maximum Volume Inscribed Ellipsoid: A New Simplex-Structured Matrix Factorization Framework via Facet Enumeration and Convex Optimization ⋮ Using multiobjective optimization to map the entropy region ⋮ Sum of Squares Certificates for Containment of $\mathcal{H}$-Polytopes in $\mathcal{V}$-Polytopes ⋮ The CONEstrip Algorithm ⋮ Continuous Maps from Spheres Converging to Boundaries of Convex Hulls ⋮ Computing monotone disjoint paths on polytopes ⋮ Generating all vertices of a polyhedron is hard ⋮ IMPRECISE MARKOV CHAINS AND THEIR LIMIT BEHAVIOR ⋮ Complexity of approximating the vertex centroid of a polyhedron ⋮ A Derivative-Free Method for Structured Optimization Problems ⋮ Converting between quadrilateral and standard solution sets in normal surface theory ⋮ Applications of polyhedral computations to the analysis and verification of hardware and software systems ⋮ Two variations of graph test in double description method ⋮ On the no-signaling approach to quantum nonlocality ⋮ Enumerating Vertices of 0/1-Polyhedra associated with 0/1-Totally Unimodular Matrices ⋮ Multinomial models with linear inequality constraints: overview and improvements of computational methods for Bayesian inference ⋮ Forbidden Vertices ⋮ Inner approximation algorithm for solving linear multiobjective optimization problems ⋮ A reverse search algorithm for the neighborhood problem ⋮ Accelerating Fourier–Motzkin elimination using bit pattern trees ⋮ Enumerating a subset of the integer points inside a Minkowski sum ⋮ Multiparametric demand transportation problem ⋮ AN ORACLE-BASED, OUTPUT-SENSITIVE ALGORITHM FOR PROJECTIONS OF RESULTANT POLYTOPES
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A simple and relatively efficient triangulation of the n-cube
- Computing extreme rays of the metric cone for seven points
- A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
- Polytope pairs and their relationship to linear programming
- Incremental convex hull algorithms are not output sensitive
- An optimal convex hull algorithm in any fixed dimension
- Selected bibliography on degeneracy
- Bounds on the number of vertices of perturbed polyhedra
- Efficient enumeration of the vertices of polyhedra associated with network LP's
- The nature and meaning of perturbations in geometric computing
- Projections of 3-polytopes
- The Complexity of Vertex Enumeration Methods
- Finding the convex hull facet by facet
- Lectures on Polytopes
- The quickhull algorithm for convex hulls
- An Algorithm for Convex Polytopes
- The maximum numbers of faces of a convex polytope
This page was built for publication: How good are convex hull algorithms?
