COMBINATORIAL FACE ENUMERATION IN CONVEX POLYTOPES

Let P be a d-dimensional convex polytope with n facets F1, F2,...,F(n). The (combinatorial) representation of a face F of P is the set of facet indices j such that F subset-of F(j). Given the representations of all vertices of P, the combinatorial face enumeration problem is to enumerate all faces in terms of their representations. In this paper we propose two algorithms for the combinatorial face enumeration problem. The first algorithm enumerates all faces in time O(f2d min{m, n}), where f and m denotes the number of faces and vertices, respectively. For the case of simple polytopes, the second algorithm solves the problem in O(fd) time, provided that a good orientation of the graph of the polytope is also given as input.