Abstract

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.

Details

Actions