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)

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. ⋮ Enumerating edge-constrained triangulations and edge-constrained non-crossing geometric spanning trees ⋮ Error control in polytope computations ⋮ Optimizing the double description method for normal surface enumeration ⋮ Bernstein's second theorem and Viro's method for sparse polynomial systems in chemistry ⋮ On the convex hull of projective planes ⋮ Is a finite intersection of balls covered by a finite union of balls in Euclidean spaces? ⋮ Complexity of methods for approximating convex compact bodies by double description polytopes and complexity bounds for a hyperball ⋮ Note on the complexity of the mixed-integer hull of a polyhedron ⋮ Unbounded-time safety verification of guarded LTI models with inputs by abstract acceleration ⋮ Constant memory routing in quasi-planar and quasi-polyhedral graphs ⋮ The stable set polytope of claw-free graphs with stability number at least four. II. Striped graphs are \(\mathcal{G}\)-perfect ⋮ Combinatorial optimization and small polytopes ⋮ Generalized pattern search methods for a class of nonsmooth optimization problems with structure ⋮ Generating rooted triangulations without repetitions ⋮ The vertex set of a \(0/1\)-polytope is strongly \(\mathcal P\)-enumerable ⋮ A problem in enumerating extreme points, and an efficient algorithm for one class of polytopes ⋮ A polyhedral model for enumeration and optimization over the set of circuits ⋮ Pruning Algorithms for Pretropisms of Newton Polytopes ⋮ Iterative Refinement for Linear Programming ⋮ New gain-scheduling control conditions for time-varying delayed LPV systems ⋮ Probabilistic feasibility guarantees for solution sets to uncertain variational inequalities ⋮ Two variations of graph test in double description method ⋮ Resilient multi-dimensional consensus in adversarial environment ⋮ A reverse search algorithm for the neighborhood problem ⋮ On local transformation of polygons with visibility properties. ⋮ Linearly constrained global optimization: a general solution algorithm with applications. ⋮ Pivot rules for linear programming: A survey on recent theoretical developments ⋮ A Portable Parallel Implementation of the lrs Vertex Enumeration Code ⋮ Extreme points of the credal sets generated by comparative probabilities ⋮ Efficient enumeration of the vertices of polyhedra associated with network LP's ⋮ Tabu search and finite convergence ⋮ Multiparametric demand transportation problem ⋮ A duality theorem for the ic-resurgence of edge ideals ⋮ Estimating the number of vertices of a polyhedron ⋮ The symplectic geometry of closed equilateral random walks in 3-space ⋮ Lagrangian methods for approximating the viability kernel in high-dimensional systems

Cites Work

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