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: from sage.geometry.polyhedron.combinatorial_polyhedron.polyhedron_face_lattice \
....: import PolyhedronFaceLattice
sage: P = polytopes.octahedron()
sage: C = CombinatorialPolyhedron(P)
sage: all_faces = PolyhedronFaceLattice(C)

>>> 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)

See also

base, PolyhedronFaceLattice.

AUTHOR:

  • Jonathan Kliem (2019-04)

class sage.geometry.polyhedron.combinatorial_polyhedron.polyhedron_face_lattice.PolyhedronFaceLattice[source]

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: 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

>>> 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

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[source]
get_face(dimension, index)[source]

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: 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

>>> 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