Ask Your Question

Is it possible to compute the face lattice of a polytope from its vertex-facet incidences?

asked 2016-11-16 01:13:31 +0200

guillermo gravatar image

HI there,

I wonder if within sage it is possible to compute the face lattice of a polytope from its vertex-facet incidences. There is a known algorithm by Kaibel and Pfetsch (see, and we wonder if it has already been implemented in Sage.

Thanks, and regards, Guillermo

edit retag flag offensive close merge delete

2 Answers

Sort by ยป oldest newest most voted

answered 2019-08-27 22:04:46 +0200

jipilab gravatar image

From Sage version 8.9+, on, the class CombinatorialPolyhedron can do just that.

Here is an example with your suggested Egyptian pyramid:

sage: ep = CombinatorialPolyhedron([[4,3,2,1],[4,3,0],[4,2,0],[3,1,0],[2,1,0]]); ep
A 3-dimensional combinatorial polyhedron with 5 facets
sage: fl_ep = ep.face_lattice(); fl_ep
Finite lattice containing 20 elements
sage: ep.f_vector()
(1, 5, 8, 5, 1)
sage: ep_poly = polytopes.regular_polygon(4).pyramid()
sage: fl_ep_poly = ep_poly.face_lattice()
sage: fl_ep_poly.is_isomorphic(fl_ep)

So far, there are a few things you can call on ep like edge graph, and ridges, and a fast iterator on the faces.

edit flag offensive delete link more

answered 2016-11-16 08:42:19 +0200

slelievre gravatar image

updated 2016-11-16 08:42:35 +0200

By searching the documentation or the source files of Sage, you can get an answer.

Searching doc:

sage: search_doc('Kaibel')
html/en/reference/geometry/sage/geometry/polyhedron/base.html:1166:<tr><td class="label"><a class="fn-backref" href="#id1">[KP2002]</a></td><td>Volker Kaibel and Marc E. Pfetsch, &#8220;Computing the Face

Searching source:

sage: search_src('Kaibel')
geometry/polyhedron/            Volker Kaibel and Marc E. Pfetsch, "Computing the Face

Online documentation (append the result of "search_doc" to "").

edit flag offensive delete link more


Hi slelievre,

Thank you for your reply. Sage computes the face lattice of a polytope using Kaibel and Pfetsch's algorithm. So a polytope must be given. However, for you to construct a polytope in Sage you need either vertex coordinates or hyperplane equations; that is, you need a geometric realisation of the polytope.

Vertex-facet incidences is a combinatorial object which doesn't know about a geometric realisation. For instance, the following gives the vertex-facet incidences of the Egyptian pyramid [[4,3,2,1],[4,3,0],[4,2,0],[3,1,0],[2,1,0]], where the [4, 3, 2, 1] are the vertices of one facet.

guillermo gravatar imageguillermo ( 2016-11-16 08:58:04 +0200 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2016-11-16 01:13:31 +0200

Seen: 509 times

Last updated: Aug 27 '19