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

Fukuda, Komei; Rosta, Vera

Comput. Geom. 4, No. 4, 191-198 (1994).

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.

MSC:

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

Keywords:

convex polytope; combinatorial face enumeration problem

Software:

VertexEnumeration

References:

[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