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

DOI10.1016/0925-7721(95)00049-6MaRDI QIDQ2482881zbMATH OpenOpenAlexFDO

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

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 hyperplanesface enumeration problemoptimal vertex problems for polyhedrarestricted vertex problemvertex enumeration problem

Mathematics Subject Classification ID

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

Recommendations

• The Complexity of Vertex Enumeration Methods
• Combinatorial face enumeration in convex polytopes
• How good are convex hull algorithms?
• The vertex set of a \(0/1\)-polytope is strongly \(\mathcal P\)-enumerable
• A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra

Cites work

• A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
• An Algorithm for Determining Irrelevant Constraints and all Vertices in Systems of Linear Inequalities
• An Algorithm for Finding All Vertices of Convex Polyhedral Sets
• Finding all minimum-cost perfect matchings in Bipartite graphs
• Finding all the perfect matchings in bipartite graphs
• scientific article; zbMATH DE number 4032498 (Why is no real title available?)
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 193411 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3345859 (Why is no real title available?)
• scientific article; zbMATH DE number 3078984 (Why is no real title available?)
• Reverse search for enumeration
• Segments in enumerating faces
• Some NP-complete problems in linear programming
• The Complexity of Enumeration and Reliability Problems
• The Complexity of Vertex Enumeration Methods

Cited in

(26)

• The vertex set of a \(0/1\)-polytope is strongly \(\mathcal P\)-enumerable
• The Benders decomposition algorithm: a literature review
• Identification of unidentified equality constraints for integer programming problems
• Compactness criteria for real algebraic sets and Newton polyhedra
• Linearly constrained global optimization: a general solution algorithm with applications.
• Computing the face lattice of a polytope from its vertex-facet incidences
• The Lasso problem and uniqueness
• Robust fitting in computer vision: easy or hard?
• The maximal descriptor index set for a face of a convex polyhedral set and some applications
• A note on the selection of Benders' cuts
• The fundamental theorem of linear programming: extensions and applications
• Pooling problems with polynomial-time algorithms
• A common formula to compute the efficient sets of a class of multiple objective linear programming problems
• A validation and verification tool for global optimization solvers
• A POLYNOMIAL ALGORITHM FOR ENUMERATING ALL VERTICES OF A BASE POLYHEDRON
• A complete description of cones and polytopes including hypervolumes of all facets of a polytope
• Farkas certificates and minimal witnesses for probabilistic reachability constraints
• A Closest Benders Cut Selection Scheme for Accelerating the Benders Decomposition Algorithm
• Technical note -- There's no free lunch: on the hardness of choosing a correct big-M in bilevel optimization
• Convex relaxation of discrete vector-valued optimization problems
• The Minimum Euclidean-Norm Point in a Convex Polytope: Wolfe's Combinatorial Algorithm is Exponential
• Directed acyclic decomposition of Kuramoto equations
• A new method to solve bi-level quadratic linear fractional programming problems
• Counting and enumeration complexity with application to multicriteria scheduling
• Generating all vertices of a polyhedron is hard
• Eigenpolytope Universality and Graphical Designs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2482881)