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 polyhedronHrep – 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
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 theface_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.- get_face(dimension, index)[source]¶
Return the face of dimension
dimension
and indexindex
.INPUT:
dimension
– dimension of the faceindex
– index of the facenames
– ifTrue
returns the names of the[vertices, rays, lines]
as given on initialization ofCombinatorialPolyhedron
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