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.

Published in:
Computational Geometry, 4, 191-198
PRO 94.12

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

Rate this document:

Rate this document:
(Not yet reviewed)