ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Tue, 27 Aug 2019 22:04:46 +0200Is it possible to compute the face lattice of a polytope from its vertex-facet incidences?https://ask.sagemath.org/question/35605/is-it-possible-to-compute-the-face-lattice-of-a-polytope-from-its-vertex-facet-incidences/ 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 https://arxiv.org/pdf/math/0106043.pdf), and we wonder if it has already been implemented in Sage.
Thanks, and regards,
GuillermoWed, 16 Nov 2016 01:13:31 +0100https://ask.sagemath.org/question/35605/is-it-possible-to-compute-the-face-lattice-of-a-polytope-from-its-vertex-facet-incidences/Answer by slelievre for <p>HI there,</p>
<p>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 <a href="https://arxiv.org/pdf/math/0106043.pdf">https://arxiv.org/pdf/math/0106043.pdf</a>), and we wonder if it has already been implemented in Sage.</p>
<p>Thanks, and regards,
Guillermo</p>
https://ask.sagemath.org/question/35605/is-it-possible-to-compute-the-face-lattice-of-a-polytope-from-its-vertex-facet-incidences/?answer=35607#post-id-35607By 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, “Computing the Face
Searching source:
sage: search_src('Kaibel')
geometry/polyhedron/base.py:3195: Volker Kaibel and Marc E. Pfetsch, "Computing the Face
Online documentation (append the result of "search_doc" to "[http://doc.sagemath.org/](http://doc.sagemath.org/)").
[http://doc.sagemath.org/html/en/reference/geometry/sage/geometry/polyhedron/base.html#sage.geometry.polyhedron.base.Polyhedron_base.face_lattice](http://doc.sagemath.org/html/en/reference/geometry/sage/geometry/polyhedron/base.html#sage.geometry.polyhedron.base.Polyhedron_base.face_lattice)Wed, 16 Nov 2016 08:42:19 +0100https://ask.sagemath.org/question/35605/is-it-possible-to-compute-the-face-lattice-of-a-polytope-from-its-vertex-facet-incidences/?answer=35607#post-id-35607Comment by guillermo for <p>By searching the documentation or the source files of Sage, you can get an answer.</p>
<p>Searching doc:</p>
<pre><code>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
</code></pre>
<p>Searching source:</p>
<pre><code>sage: search_src('Kaibel')
geometry/polyhedron/base.py:3195: Volker Kaibel and Marc E. Pfetsch, "Computing the Face
</code></pre>
<p>Online documentation (append the result of "search_doc" to "<a href="http://doc.sagemath.org/">http://doc.sagemath.org/</a>").</p>
<p><a href="http://doc.sagemath.org/html/en/reference/geometry/sage/geometry/polyhedron/base.html#sage.geometry.polyhedron.base.Polyhedron_base.face_lattice">http://doc.sagemath.org/html/en/reference/geometry/sage/geometry/polyhedron/base.html#sage.geometry.polyhedron.base.Polyhedron_base.face_lattice</a></p>
https://ask.sagemath.org/question/35605/is-it-possible-to-compute-the-face-lattice-of-a-polytope-from-its-vertex-facet-incidences/?comment=35608#post-id-35608Hi 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.Wed, 16 Nov 2016 08:58:04 +0100https://ask.sagemath.org/question/35605/is-it-possible-to-compute-the-face-lattice-of-a-polytope-from-its-vertex-facet-incidences/?comment=35608#post-id-35608Answer by jipilab for <p>HI there,</p>
<p>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 <a href="https://arxiv.org/pdf/math/0106043.pdf">https://arxiv.org/pdf/math/0106043.pdf</a>), and we wonder if it has already been implemented in Sage.</p>
<p>Thanks, and regards,
Guillermo</p>
https://ask.sagemath.org/question/35605/is-it-possible-to-compute-the-face-lattice-of-a-polytope-from-its-vertex-facet-incidences/?answer=47629#post-id-47629From 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)
True
So far, there are a few things you can call on `ep` like edge graph, and ridges, and a fast iterator on the faces.Tue, 27 Aug 2019 22:04:46 +0200https://ask.sagemath.org/question/35605/is-it-possible-to-compute-the-face-lattice-of-a-polytope-from-its-vertex-facet-incidences/?answer=47629#post-id-47629