Analysis of backtrack algorithms for listing all vertices and all faces of a convex polyhedron
1997; Elsevier BV; Volume: 8; Issue: 1 Linguagem: Inglês
10.1016/0925-7721(95)00049-6
ISSN1879-081X
AutoresKomei Fukuda, Thomas M. Liebling, François Margot,
Tópico(s)Complexity and Algorithms in Graphs
ResumoIn 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.
Referência(s)