Computing the Face Lattice of a Polytope from its Vertex-Facet Incidences
| dc.creator | Kaibel, Volker | |
| dc.creator | Pfetsch, Marc E. | |
| dc.date | 2001-06-07 | |
| dc.date | 2002-08-14 | |
| dc.date.accessioned | 2026-07-07T04:42:01Z | |
| dc.date.available | 2026-07-07T04:42:01Z | |
| dc.description | 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. | |
| dc.description | 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 | |
| dc.identifier | https://arxiv.org/abs/math/0106043 | |
| dc.identifier | http://arxiv.org/abs/math/0106043 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/61601 | |
| dc.subject | Metric Geometry | |
| dc.subject | Combinatorics | |
| dc.subject | 68R05 68U05 52B11 68Q25 52C40 | |
| dc.title | Computing the Face Lattice of a Polytope from its Vertex-Facet Incidences | |
| dc.type | text |