Combinatorial face enumeration in convex polytopes
Let P be a d-dimensional convex polytope with n facets F1,F2,....,Fn. The (combinatorial) representation of a face F of P is the set of facet indices j such that F c Fj. 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 que propose two algorithms for the combinatorial face enumeration problem. the first algorithm enumerates all faces in time O(f^2d minm.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 polytope is also given as input.
- View record in Web of Science
Record created on 2006-02-13, modified on 2016-08-08