Computing the face lattice of a polytope from its vertex-facet incidences

摘要

We give an algorithm that constructs the Hasse diagram of the face lattice of a convex polytope P from its vertexfacet incidences in time O(min{n,m}·α·#Phi#}, where n is the number of vertices, m is the number of facets, α is the number of vertex-facet incidences, and #Phi# is the total number of faces of P. This improves results of Fukuda and Rosta [Computational Geometry 4 (4) (1994) 191-198], who described an algorithm for enumerating all faces of a d-polytope in O(min{n,m}·d·#Phi#~2) steps. For simple or simplicial d-polytope our algorithm can be specialized to run in time O(d·α·#Phi#). Furthermore, applications of the algorithm to other atomic lattices are discussed, e.g., to face lattices of oriented matroids.