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

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.

Published in:
Computational Geometry, 8, 1-12
PRO 1997.03; PRO 96.01

 Record created 2006-02-13, last modified 2018-01-27

Rate this document:

Rate this document:
(Not yet reviewed)