2001/06/07 by Volker Kaibel, Kaibel, Volker, Marc E. Pfetsch +1
Mathematics · #68R05 68U05 52B11 68Q25 52C40 #Combinatorics (math.CO) #FOS: Mathematics #Metric Geometry (math.MG) #math.CO #math.MG #msc:52B11 #msc:52C40 #msc:68Q25 #msc:68R05 #msc:68U05
paper · pdf · doi:10.48550/arxiv.math/0106043
14 pages; to appear in: Comput. Geom.; the new version contains some minor extensions and corrections as well as a more detailed treatment of oriented matroids
arxiv created 2002/08/14 · arxiv updated 2009/11/30
We give an algorithm that constructs the Hasse diagram of the face lattice of a convex polytope P from its vertex-facet incidences in time O(minn,m*a*f), where n is the number of vertices, m is the number of facets, a is the number of vertex-facet incidences, and f is the total number of faces of P. This improves results of Fukuda and Rosta (1994), who described an algorithm for enumerating all faces of a d-polytope in O(minn,m*d*f2) steps. For simple or simplicial d-polytopes our algorithm can be specialized to run in time O(d*a*f). Furthermore, applications of the algorithm to other atomic lattices are discussed, e.g., to face lattices of oriented matroids.