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
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
