PolyhedronFaceLattice

This module provides a class that stores and sorts all faces of the polyhedron.

CombinatorialPolyhedron implicitly uses this class to generate the face lattice of a polyhedron.

Terminology in this module:

• Vrep – [vertices, rays, lines] of the polyhedron

• Hrep – inequalities and equations of the polyhedron

• Facets – facets of the polyhedron

• Coatoms – the faces from which all others are constructed in the face iterator. This will be facets or Vrep. In non-dual mode, faces are constructed as intersections of the facets. In dual mode, the are constructed theoretically as joins of vertices. The coatoms are repsented as incidences with the atoms they contain.

• Atoms – facets or Vrep depending on application of algorithm. Atoms are repsented as incidences of coatoms they are contained in.

• Vrepresentation – represents a face by a list of Vrep it contains

• Hrepresentation – represents a face by a list of Hrep it is contained in

• bit representation – represents incidences as uint64_t-array, where each bit represents one incidence. There might be trailing zeros, to fit alignment requirements. In most instances, faces are represented by the bit representation, where each bit corresponds to an atom.

EXAMPLES:

Sage

sage: from sage.geometry.polyhedron.combinatorial_polyhedron.polyhedron_face_lattice \
....: import PolyhedronFaceLattice
sage: P = polytopes.octahedron()
sage: C = CombinatorialPolyhedron(P)
sage: all_faces = PolyhedronFaceLattice(C)

Python

>>> from sage.all import *
>>> from sage.geometry.polyhedron.combinatorial_polyhedron.polyhedron_face_lattice import PolyhedronFaceLattice
>>> P = polytopes.octahedron()
>>> C = CombinatorialPolyhedron(P)
>>> all_faces = PolyhedronFaceLattice(C)

Sage Live

from sage.geometry.polyhedron.combinatorial_polyhedron.polyhedron_face_lattice \
import PolyhedronFaceLattice
P = polytopes.octahedron()
C = CombinatorialPolyhedron(P)
all_faces = PolyhedronFaceLattice(C)

See also

base, PolyhedronFaceLattice.

AUTHOR:

• Jonathan Kliem (2019-04)

class sage.geometry.polyhedron.combinatorial_polyhedron.polyhedron_face_lattice.PolyhedronFaceLattice

Bases: object

A class to generate incidences of CombinatorialPolyhedron.

On initialization all faces of the given CombinatorialPolyhedron are added and sorted (except coatoms). The incidences can be used to generate the face_lattice.

Might generate the faces of the dual polyhedron for speed.

INPUT:

• baseCombinatorialPolyhedron

See also

_record_all_faces(), _record_all_faces_helper(), face_lattice(), _compute_face_lattice_incidences().

EXAMPLES:

Sage

sage: P = polytopes.Birkhoff_polytope(3)
sage: C = CombinatorialPolyhedron(P)
sage: C._record_all_faces()  # indirect doctests
sage: C.face_lattice()                                                          # needs sage.combinat
Finite lattice containing 50 elements

Python

>>> from sage.all import *
>>> P = polytopes.Birkhoff_polytope(Integer(3))
>>> C = CombinatorialPolyhedron(P)
>>> C._record_all_faces()  # indirect doctests
>>> C.face_lattice()                                                          # needs sage.combinat
Finite lattice containing 50 elements

Sage Live

P = polytopes.Birkhoff_polytope(3)
C = CombinatorialPolyhedron(P)
C._record_all_faces()  # indirect doctests
C.face_lattice()                                                          # needs sage.combinat

ALGORITHM:

The faces are recorded with FaceIterator in Bit-representation. Once created, all level-sets but the coatoms are sorted with merge sort. Non-trivial incidences of elements whose rank differs by 1 are determined by intersecting with all coatoms. Then each intersection is looked up in the sorted level sets.

dual

get_face(dimension, index)

Return the face of dimension dimension and index index.

INPUT:

• dimension – dimension of the face

• index – index of the face

• names – if True returns the names of the [vertices, rays, lines] as given on initialization of CombinatorialPolyhedron

EXAMPLES:

Sage

sage: from sage.geometry.polyhedron.combinatorial_polyhedron.polyhedron_face_lattice \
....:         import PolyhedronFaceLattice
sage: P = polytopes.permutahedron(4)
sage: C = CombinatorialPolyhedron(P)
sage: F = PolyhedronFaceLattice(C)
sage: it = C.face_generator(dimension=1)
sage: face = next(it)
sage: index = F._find_face_from_combinatorial_face(face)
sage: F.get_face(face.dimension(), index).ambient_Vrepresentation()
(A vertex at (2, 1, 4, 3), A vertex at (1, 2, 4, 3))
sage: face.ambient_Vrepresentation()
(A vertex at (2, 1, 4, 3), A vertex at (1, 2, 4, 3))
sage: all(F.get_face(face.dimension(),
....:                F._find_face_from_combinatorial_face(face)).ambient_Vrepresentation() ==
....:     face.ambient_Vrepresentation() for face in it)
True

sage: P = polytopes.twenty_four_cell()
sage: C = CombinatorialPolyhedron(P)
sage: F = PolyhedronFaceLattice(C)
sage: it = C.face_generator()
sage: face = next(it)
sage: while (face.dimension() == 3): face = next(it)
sage: index = F._find_face_from_combinatorial_face(face)
sage: F.get_face(face.dimension(), index).ambient_Vrepresentation()
(A vertex at (-1/2, 1/2, -1/2, -1/2),
 A vertex at (-1/2, 1/2, 1/2, -1/2),
 A vertex at (0, 0, 0, -1))
sage: all(F.get_face(face.dimension(),
....:                F._find_face_from_combinatorial_face(face)).ambient_V_indices() ==
....:     face.ambient_V_indices() for face in it)
True

Python

>>> from sage.all import *
>>> from sage.geometry.polyhedron.combinatorial_polyhedron.polyhedron_face_lattice         import PolyhedronFaceLattice
>>> P = polytopes.permutahedron(Integer(4))
>>> C = CombinatorialPolyhedron(P)
>>> F = PolyhedronFaceLattice(C)
>>> it = C.face_generator(dimension=Integer(1))
>>> face = next(it)
>>> index = F._find_face_from_combinatorial_face(face)
>>> F.get_face(face.dimension(), index).ambient_Vrepresentation()
(A vertex at (2, 1, 4, 3), A vertex at (1, 2, 4, 3))
>>> face.ambient_Vrepresentation()
(A vertex at (2, 1, 4, 3), A vertex at (1, 2, 4, 3))
>>> all(F.get_face(face.dimension(),
...                F._find_face_from_combinatorial_face(face)).ambient_Vrepresentation() ==
...     face.ambient_Vrepresentation() for face in it)
True

>>> P = polytopes.twenty_four_cell()
>>> C = CombinatorialPolyhedron(P)
>>> F = PolyhedronFaceLattice(C)
>>> it = C.face_generator()
>>> face = next(it)
>>> while (face.dimension() == Integer(3)): face = next(it)
>>> index = F._find_face_from_combinatorial_face(face)
>>> F.get_face(face.dimension(), index).ambient_Vrepresentation()
(A vertex at (-1/2, 1/2, -1/2, -1/2),
 A vertex at (-1/2, 1/2, 1/2, -1/2),
 A vertex at (0, 0, 0, -1))
>>> all(F.get_face(face.dimension(),
...                F._find_face_from_combinatorial_face(face)).ambient_V_indices() ==
...     face.ambient_V_indices() for face in it)
True

Sage Live

from sage.geometry.polyhedron.combinatorial_polyhedron.polyhedron_face_lattice \
        import PolyhedronFaceLattice
P = polytopes.permutahedron(4)
C = CombinatorialPolyhedron(P)
F = PolyhedronFaceLattice(C)
it = C.face_generator(dimension=1)
face = next(it)
index = F._find_face_from_combinatorial_face(face)
F.get_face(face.dimension(), index).ambient_Vrepresentation()
face.ambient_Vrepresentation()
all(F.get_face(face.dimension(),
               F._find_face_from_combinatorial_face(face)).ambient_Vrepresentation() ==
    face.ambient_Vrepresentation() for face in it)
P = polytopes.twenty_four_cell()
C = CombinatorialPolyhedron(P)
F = PolyhedronFaceLattice(C)
it = C.face_generator()
face = next(it)
while (face.dimension() == 3): face = next(it)
index = F._find_face_from_combinatorial_face(face)
F.get_face(face.dimension(), index).ambient_Vrepresentation()
all(F.get_face(face.dimension(),
               F._find_face_from_combinatorial_face(face)).ambient_V_indices() ==
    face.ambient_V_indices() for face in it)

Make live