Combinatorial face enumeration in convex polytopes. (English) Zbl 0811.68119

Summary: Let \(P\) be a \(d\)-dimensional convex polytope with \(n\) facets \(F_ 1\), \(F_ 2, \dots, F_ n\). The (combinatorial) representation of a fact \(F\) of \(P\) is the set of fact indices \(j\) such that \(F \subset 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.
We propose two algorithms for the combinatorial face enumeration problem. The first algorithm enumerates all faces in time \(O(f^ 2d \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.


68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68Q25 Analysis of algorithms and problem complexity
68R05 Combinatorics in computer science
52B11 \(n\)-dimensional polytopes
05A15 Exact enumeration problems, generating functions
Full Text: DOI


[1] Avis, D.; Fukuda, K., A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra, Discrete Comput. Geom., 8, 295-313 (1992) · Zbl 0752.68082
[2] Fukuda, K.; Mizukoshi, I., Mathematica package: Vertex enumeration for convex polyhedra and hyperplane arrangements, Version 0.41 Beta (1992), Graduate School of Systems Management, University of Tsukuba: Graduate School of Systems Management, University of Tsukuba Tokyo, available via anonymous ftp from cs.sunysb.edu (directory pub/Combinatorica)
[3] Fukuda, K.; Saito, S.; Tamura, A., Combinatorial face enumeration in arrangements and oriented matroids, Discrete Appl. Math., 31, 141-149 (1991) · Zbl 0752.05016
[4] Grünbaum, B., Convex Polytopes (1967), Interscience: Interscience New York · Zbl 0163.16603
[5] Kalai, G., A simple way to tell a simple polytope from its graph, J. Combin.Theory Ser.A, 49, 381-383 (1988) · Zbl 0673.05087
[6] McMullen, P.; Shephard, G. C., Convex Polytopes and the Upper Bound Conjecture (1971), Cambridge, Univ. Press: Cambridge, Univ. Press Cambridge · Zbl 0217.46702
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.