A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra

DOI10.1007/BF02293050zbMath0752.68082DBLPjournals/dcg/AvisF92OpenAlexW4234356172WikidataQ30051803 ScholiaQ30051803MaRDI QIDQ1199131

David Avis, Komei Fukuda

Publication date: 16 January 1993

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02293050

zbMATH Keywords

pivot-based algorithm enumeration problems in computational geometry

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (only showing first 100 items - show all)

Computing Gröbner Fans of Toric Ideals ⋮ Farkas Certificates and Minimal Witnesses for Probabilistic Reachability Constraints ⋮ ENUMERATING TRIANGULATIONS IN GENERAL DIMENSIONS ⋮ Convex hull of planarh-polyhedra ⋮ Bounding the plastic strength of polycrystalline solids by linear-comparison homogenization methods ⋮ A Gibbs Sampler for a Class of Random Convex Polytopes ⋮ Optimal distributions for multiplex logistic networks ⋮ Minimal balanced collections and their application to core stability and other topics of game theory ⋮ Revisited aspects of the local set in CHSH Bell scenario ⋮ Robust homecare service capacity planning ⋮ Combinatorial and geometric approaches to counting problems on linear matroids, graphic arrangements, and partial orders ⋮ An effective solution to convex 1-body \(N\)-representability ⋮ Coercive polynomials: stability, order of growth, and Newton polytopes ⋮ Fast enumeration algorithms for non-crossing geometric graphs ⋮ Extended formulations in combinatorial optimization ⋮ H _∞ PID controller design for Lur’e systems and its application to a ball and wheel apparatus ⋮ A complete description of cones and polytopes including hypervolumes of all facets of a polytope ⋮ Extended formulations in combinatorial optimization ⋮ A method of transferring polyhedron between the intersection-form and the sum-form ⋮ Algebraic Attacks Galore! ⋮ A validation and verification tool for global optimization solvers ⋮ DECOMPOSITION AND PARALLELIZATION TECHNIQUES FOR ENUMERATING THE FACETS OF COMBINATORIAL POLYTOPES ⋮ Extended convex hull ⋮ A formalization of convex polyhedra based on the simplex method ⋮ Algorithm 998 ⋮ Testing for Inequality Constraints in Singular Models by Trimming or Winsorizing the Variance Matrix ⋮ On computing ELECTRE's credibility indices under partial information ⋮ Enumerating Vertices of Covering Polyhedra with Totally Unimodular Constraint Matrices ⋮ Generating all vertices of a polyhedron is hard ⋮ Modeling and Managing Uncertainty in Process Planning and Scheduling ⋮ A sweep-plane algorithm for generating random tuples in simple polytopes ⋮ Enumerating Vertices of 0/1-Polyhedra associated with 0/1-Totally Unimodular Matrices ⋮ Coercive Polynomials and Their Newton Polytopes ⋮ Local Graph Stability in Exponential Family Random Graph Models ⋮ Minimum norm interpolation in the ℓ1(ℕ) space ⋮ Inner approximation algorithm for solving linear multiobjective optimization problems ⋮ Finiteness of relative equilibria of the four-body problem ⋮ Constructive solution of inverse parametric linear/quadratic programming problems ⋮ Explicit robustness and fragility margins for linear discrete systems with piecewise affine control law ⋮ A linear optimization oracle for zonotope computation ⋮ \texttt{mplrs}: a scalable parallel vertex/facet enumeration code ⋮ Average complexity of a gift-wrapping algorithm for determining the convex hull of randomly given points ⋮ Combinatorial face enumeration in convex polytopes ⋮ Memory-efficient enumeration of constrained spanning trees ⋮ Enumerating non-crossing minimally rigid frameworks ⋮ On the complexity of some basic problems in computational convexity. I. Containment problems ⋮ Output-Sensitive Algorithms for Enumerating the Extreme Nondominated Points of Multiobjective Combinatorial Optimization Problems ⋮ Enumerating trichromatic triangles containing the origin in linear time ⋮ On planar path transformation ⋮ Enumeration of Nash equilibria for two-player games ⋮ On attainability of Kendall's tau matrices and concordance signatures ⋮ A branch-price-and-cut algorithm for the minimum evolution problem ⋮ Equilibrium computation of the Hart and Mas-Colell bargaining model ⋮ How good are convex hull algorithms? ⋮ Convex hulls, oracles, and homology ⋮ From the zonotope construction to the Minkowski addition of convex polytopes ⋮ Constrained random matching ⋮ Segments in enumerating faces ⋮ Bounds on the complexity of halfspace intersections when the bounded faces have small dimension ⋮ Criss-cross methods: A fresh view on pivot algorithms ⋮ Algebraic and numerical techniques for the computation of matrix determinants ⋮ Computing convex hulls and counting integer points with \texttt{polymake} ⋮ Reverse search for enumeration ⋮ Robinsonian matrices: recognition challenges ⋮ A thrust network approach to the equilibrium problem of unreinforced masonry vaults via polyhedral stress functions ⋮ A mixed lumped stress-displacement approach to the elastic problem of masonry walls ⋮ Mixed-volume computation by dynamic lifting applied to polynomial system solving ⋮ Fluid approximation of Petri net models with relatively small populations ⋮ \(\mathcal{H}_2\) control and filtering of discrete-time LPV systems exploring statistical information of the time-varying parameters ⋮ On the occurrence probability of local binary patterns: a theoretical study ⋮ Monte Carlo sampling can be used to determine the size and shape of the steady-state flux space ⋮ An SMT-based approach to weak controllability for disjunctive temporal problems with uncertainty ⋮ Unmixing the mixed volume computation ⋮ A procedure for computing the log canonical threshold of a binomial ideal ⋮ The stable set polytope of icosahedral graphs ⋮ On the calculation of a membership function for the solution of a fuzzy linear optimization problem ⋮ Pattern search in the presence of degenerate linear constraints ⋮ SMEFTs living on the edge: determining the UV theories from positivity and extremality ⋮ 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 ⋮ On perfect Nash equilibria of polymatrix games ⋮ A new approach to output-sensitive construction of Voronoi diagrams and Delaunay triangulations ⋮ The two variable per inequality abstract domain ⋮ Errors bounds for finite approximations of coherent lower previsions on finite probability spaces ⋮ An algorithm for approximate multiparametric linear programming ⋮ Characterizing coherence, correcting incoherence ⋮ An algorithm to find the lineality space of the positive hull of a set of vectors ⋮ A basis enumeration algorithm for linear systems with geometric applications ⋮ Graph decompositions for demographic loop analysis ⋮ On polyhedral projection and parametric programming ⋮ Efficient edge-skeleton computation for polytopes defined by oracles ⋮ Enumerating constrained non-crossing minimally rigid frameworks ⋮ On globally diffeomorphic polynomial maps via Newton polytopes and circuit numbers ⋮ Flips in planar graphs ⋮ On enumerating minimal dicuts and strongly connected subgraphs ⋮ Identification of unidentified equality constraints for integer programming problems ⋮ Scenario-based portfolio model for building robust and proactive strategies ⋮ Globally tight bounds for almost differentiable functions over polytopes with application to tolerance analysis. ⋮ Analysis of backtrack algorithms for listing all vertices and all faces of a convex polyhedron.

Cites Work

This page was built for publication: A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra