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 (26)

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

This page was built for publication: Analysis of backtrack algorithms for listing all vertices and all faces of a convex polyhedron.