Analysis of backtrack algorithms for listing all vertices and all faces of a convex polyhedron.

DOI10.1016/0925-7721(95)00049-6zbMath1133.68462OpenAlexW2150961023MaRDI QIDQ2482881

Thomas M. Liebling, Komei Fukuda, Margot, François

Publication date: 25 April 2008

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0925-7721(95)00049-6

zbMATH Keywords

arrangements of hyperplanesvertex enumeration problemface enumeration problemoptimal vertex problems for polyhedrarestricted vertex problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

Farkas Certificates and Minimal Witnesses for Probabilistic Reachability Constraints, Pooling problems with polynomial-time algorithms, A common formula to compute the efficient sets of a class of multiple objective linear programming problems, A Closest Benders Cut Selection Scheme for Accelerating the Benders Decomposition Algorithm, A note on the selection of Benders' cuts, Robust fitting in computer vision: easy or hard?, Eigenpolytope Universality and Graphical Designs, A tree traversal algorithm for decision problems in knot theory and 3-manifold topology, The Lasso problem and uniqueness, The fundamental theorem of linear programming: extensions and applications, Technical Note—There’s No Free Lunch: On the Hardness of Choosing a Correct Big-M in Bilevel Optimization, The Benders decomposition algorithm: a literature review, Convex Relaxation of Discrete Vector-Valued Optimization Problems, Identification of unidentified equality constraints for integer programming problems, Compactness criteria for real algebraic sets and Newton polyhedra, A complete description of cones and polytopes including hypervolumes of all facets of a polytope, A validation and verification tool for global optimization solvers, The Minimum Euclidean-Norm Point in a Convex Polytope: Wolfe's Combinatorial Algorithm is Exponential, Counting and enumeration complexity with application to multicriteria scheduling, Generating all vertices of a polyhedron is hard, The vertex set of a \(0/1\)-polytope is strongly \(\mathcal P\)-enumerable, Directed acyclic decomposition of Kuramoto equations, A New Method To Solve Bi-Level Quadratic Linear Fractional Programming Problems, Linearly constrained global optimization: a general solution algorithm with applications., The maximal descriptor index set for a face of a convex polyhedral set and some applications, Computing the face lattice of a polytope from its vertex-facet incidences

Cites Work

• A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
• Finding all the perfect matchings in bipartite graphs
• Some NP-complete problems in linear programming
• Segments in enumerating faces
• Reverse search for enumeration
• The Complexity of Vertex Enumeration Methods
• An Algorithm for Finding All Vertices of Convex Polyhedral Sets
• The Complexity of Enumeration and Reliability Problems
• Finding all minimum-cost perfect matchings in Bipartite graphs
• An Algorithm for Determining Irrelevant Constraints and all Vertices in Systems of Linear Inequalities
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item