Analysis of Backtrack Algorithms for Listing All Vertices and All Faces of a Convex Polyhedron
| Autor: | François Margot, Komei Fukuda, Thomas M. Liebling |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Discrete mathematics
150399 Business and Management not elsewhere classified Control and Optimization Linear programming Vertex cover Computer Science Applications Vertex (geometry) Combinatorics FOS: Economics and business Computational Mathematics Linear inequality Polyhedron Computational Theory and Mathematics Face (geometry) TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY Convex polytope Geometry and Topology Algorithm Vertex enumeration problem Mathematics MathematicsofComputing_DISCRETEMATHEMATICS |
| DOI: | 10.1184/r1/6703775 |
| Popis: | In this paper, we investigate the applicability of backtrack technique to solve the vertex enumeration problem and the face enumeration problem for a convex polyhedron given by a system of linear inequalities. We show that there is a linear-time backtrack algorithm for the face enumeration problem whose space complexity is polynomial in the input size, but the vertex enumeration problem requires a backtrack algorithm to solve a decision problem, called the restricted vertex problem, for each output, which is shown to be NP-complete. Some related NP-complete problems associated with a system of linear inequalities are also discussed, including the optimal vertex problems for polyhedra and arrangements of hyperplanes. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|