Computing the Face Lattice of a Polytope from its Vertex-Facet Incidences

Details Computing the Face Lattice of a Polytope from its Vertex-Facet Incidences Computing the Face Lattice of a Polytope from its Vertex-Facet Incidences

2001-06-07

arxiv.org/abs/math/0106043v2

Mathematics

Metric Geometry

14 pages; to appear in: Comput. Geom.; the new version contains some minor extensions and corrections as well as a more detail

Scientific paper

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(min{n,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(min{n,m}*d*f^2) 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.

Affiliated with

Also associated with

No associations

Rating

Computing the Face Lattice of a Polytope from its Vertex-Facet Incidences does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Computing the Face Lattice of a Polytope from its Vertex-Facet Incidences, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computing the Face Lattice of a Polytope from its Vertex-Facet Incidences will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-459434