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

DOI10.1007/BF02293050zbMath0752.68082OpenAlexW4234356172WikidataQ30051803 ScholiaQ30051803MaRDI QIDQ1199131

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

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

Cites Work