next | previous | forward | backward | up | index | toc

# Polyhedron -- the class of all convex polyhedra

## Description

A Polyhedron represents a rational polyhedron. It can be bounded or unbounded, need not be full dimensional or may contain a proper affine subspace. It can be empty or zero dimensional. It is saved as a hash table which contains the vertices, generating rays, and the basis of the lineality space of the Polyhedron as well as the defining affine half-spaces and hyperplanes. The output of a Polyhedron looks like this:
 i1 : convexHull(matrix {{0,0,-1,-1},{2,-2,1,-1},{0,0,0,0}},matrix {{1},{0},{0}}) o1 = {ambient dimension => 3 } dimension of lineality space => 0 dimension of polyhedron => 2 number of facets => 5 number of rays => 1 number of vertices => 4 o1 : Polyhedron

This table displays a short summary of the properties of the Polyhedron. Note that the number of rays and vertices are modulo the lineality space. So for example a line in QQ^2 has one vertex and no rays. However, one can not access the above information directly, because this is just a virtual hash table generated for the output. The data defining a Polyhedron is extracted by the functions included in this package. A Polyhedron can be constructed as the convex hull (convexHull) of a set of points and a set of rays or as the intersection (intersection) of a set of affine half-spaces and affine hyperplanes.

For example, consider the square and the square with an emerging ray for the convex hull:
 i2 : V = matrix {{1,1,-1,-1},{1,-1,1,-1}} o2 = | 1 1 -1 -1 | | 1 -1 1 -1 | 2 4 o2 : Matrix ZZ <--- ZZ i3 : convexHull V o3 = {ambient dimension => 2 } dimension of lineality space => 0 dimension of polyhedron => 2 number of facets => 4 number of rays => 0 number of vertices => 4 o3 : Polyhedron i4 : R = matrix {{1},{1}} o4 = | 1 | | 1 | 2 1 o4 : Matrix ZZ <--- ZZ i5 : convexHull(V,R) o5 = {ambient dimension => 2 } dimension of lineality space => 0 dimension of polyhedron => 2 number of facets => 4 number of rays => 1 number of vertices => 3 o5 : Polyhedron

If we take the intersection of the half-spaces defined by the directions of the vertices and 1 we get the crosspolytope:
 i6 : HS = transpose V o6 = | 1 1 | | 1 -1 | | -1 1 | | -1 -1 | 4 2 o6 : Matrix ZZ <--- ZZ i7 : v = R || R o7 = | 1 | | 1 | | 1 | | 1 | 4 1 o7 : Matrix ZZ <--- ZZ i8 : P = intersection(HS,v) o8 = {ambient dimension => 2 } dimension of lineality space => 0 dimension of polyhedron => 2 number of facets => 4 number of rays => 0 number of vertices => 4 o8 : Polyhedron i9 : vertices P o9 = | -1 1 0 0 | | 0 0 -1 1 | 2 4 o9 : Matrix QQ <--- QQ

This can for example be embedded in 3-space on height 1:
 i10 : HS = HS | matrix {{0},{0},{0},{0}} o10 = | 1 1 0 | | 1 -1 0 | | -1 1 0 | | -1 -1 0 | 4 3 o10 : Matrix ZZ <--- ZZ i11 : HP = matrix {{0,0,1}} o11 = | 0 0 1 | 1 3 o11 : Matrix ZZ <--- ZZ i12 : w = matrix {{1}} o12 = | 1 | 1 1 o12 : Matrix ZZ <--- ZZ i13 : P = intersection(HS,v,HP,w) o13 = {ambient dimension => 3 } dimension of lineality space => 0 dimension of polyhedron => 2 number of facets => 4 number of rays => 0 number of vertices => 4 o13 : Polyhedron i14 : vertices P o14 = | -1 1 0 0 | | 0 0 -1 1 | | 1 1 1 1 | 3 4 o14 : Matrix QQ <--- QQ

## Functions and methods returning a convex polyhedron :

• affineHull -- computes the affine hull of a polyhedron
• affineImage -- computes the affine image of a cone or polyhedron
• affinePreimage -- computes the affine preimage of a cone or polyhedron
• bipyramid -- computes the bipyramid over a polyhedron
• coneToPolyhedron -- converts a cone to class Polyhedron
• convexHull -- computing the convex hull of points, rays and polyhedra
• crossPolytope -- computes the d-dimensional crosspolytope with diameter 2s
• cyclicPolytope -- computes the d dimensional cyclic polytope with n vertices
• dualCayley (missing documentation)
• dualCayleyFace (missing documentation)
• emptyPolyhedron -- generates the empty polyhedron in n-space
• hypercube -- computes the d-dimensional hypercube with edge length 2*s
• minkowskiSum -- computes the Minkowski sum of two convex objects
• newtonPolytope -- computes the Newton polytope of a polynomial
• polar -- computes the polar of a polyhedron
• polarFace -- computes the dual face of the polar polyhedron
• polytope -- returns a polytope of which the fan is the normal fan if it is polytopal
• pyramid -- computes the pyramid over a polyhedron
• secondaryPolytope -- computes the secondary polytope of a compact polyhedron
• statePolytope -- computes the state polytope of a homogeneous ideal
• stdSimplex -- generates the d-dimensional standard simplex

## Methods that use a convex polyhedron :

• "affineHull(Polyhedron)" -- see affineHull -- computes the affine hull of a polyhedron
• "affineImage(Matrix,Polyhedron)" -- see affineImage(Matrix,Polyhedron,Matrix) -- computes the affine image of a polyhedron
• affineImage(Matrix,Polyhedron,Matrix) -- computes the affine image of a polyhedron
• "affineImage(Polyhedron,Matrix)" -- see affineImage(Matrix,Polyhedron,Matrix) -- computes the affine image of a polyhedron
• "affinePreimage(Matrix,Polyhedron)" -- see affinePreimage(Matrix,Polyhedron,Matrix) -- computes the affine preimage of a polyhedron
• affinePreimage(Matrix,Polyhedron,Matrix) -- computes the affine preimage of a polyhedron
• "affinePreimage(Polyhedron,Matrix)" -- see affinePreimage(Matrix,Polyhedron,Matrix) -- computes the affine preimage of a polyhedron
• "areCompatible(Polyhedron,Polyhedron)" -- see areCompatible -- checks if the intersection of two cones/polyhedra is a face of each
• "bipyramid(Polyhedron)" -- see bipyramid -- computes the bipyramid over a polyhedron
• boundaryMap(ZZ,Polyhedron) (missing documentation)
• "cellDecompose(Polyhedron,Matrix)" -- see cellDecompose -- computes the regular cell decomposition
• "commonFace(Polyhedron,Polyhedron)" -- see commonFace -- checks if the intersection is a face of both Cones or Polyhedra, or of cones with fans
• Cone * Polyhedron -- computes the direct product of a cone and a polyhedron
• Cone + Polyhedron -- computes the Minkowski sum of a cone and a polyhedron
• "contains(Cone,Polyhedron)" -- see contains -- checks if the first argument contains the second argument
• "contains(List,Polyhedron)" -- see contains -- checks if the first argument contains the second argument
• "contains(Polyhedron,Cone)" -- see contains -- checks if the first argument contains the second argument
• "contains(Polyhedron,Matrix)" -- see contains -- checks if the first argument contains the second argument
• "contains(Polyhedron,Polyhedron)" -- see contains -- checks if the first argument contains the second argument
• "convexHull(Polyhedron,Polyhedron)" -- see convexHull -- computing the convex hull of points, rays and polyhedra
• dim(Polyhedron) -- computes the dimension of a polyhedron
• "directProduct(Cone,Polyhedron)" -- see directProduct(Cone,Cone) -- computes the direct product of polyhedra and cones
• "directProduct(Polyhedron,Cone)" -- see directProduct(Cone,Cone) -- computes the direct product of polyhedra and cones
• "directProduct(Polyhedron,Polyhedron)" -- see directProduct(Cone,Cone) -- computes the direct product of polyhedra and cones
• dualCayley(Polyhedron) (missing documentation)
• dualCayleyFace(Polyhedron) (missing documentation)
• "dualFaceLattice(Polyhedron)" -- see dualFaceLattice(ZZ,Polyhedron) -- computes the dual face lattice of a polyhedron
• dualFaceLattice(ZZ,Polyhedron) -- computes the dual face lattice of a polyhedron
• "ehrhart(Polyhedron)" -- see ehrhart -- calculates the Ehrhart polynomial of a polytope
• "faceFan(Polyhedron)" -- see faceFan -- computes the fan generated by the cones over the faces
• "faceLattice(Polyhedron)" -- see faceLattice(ZZ,Polyhedron) -- computes the face lattice of a polyhedron
• faceLattice(ZZ,Polyhedron) -- computes the face lattice of a polyhedron
• faceOf(Polyhedron) (missing documentation)
• "faces(ZZ,Polyhedron)" -- see faces -- computes all faces of a certain codimension of a Cone or Polyhedron
• "fVector(Polyhedron)" -- see fVector -- computes the f-vector of a Cone or Polyhedron
• "halfspaces(Polyhedron)" -- see halfspaces -- computes the defining half-spaces of a Cone or a Polyhedron
• "hyperplanes(Polyhedron)" -- see hyperplanes -- computes the defining hyperplanes of a Cone or a Polyhedron
• "incompPolyhedra(PolyhedralComplex,Polyhedron)" -- see incompPolyhedra -- returns the pairs of incompatible polyhedra
• "incompPolyhedra(Polyhedron,PolyhedralComplex)" -- see incompPolyhedra -- returns the pairs of incompatible polyhedra
• "inInterior(Matrix,Polyhedron)" -- see inInterior -- checks if a point lies in the relative interior of a Cone/Polyhedron
• "interiorLatticePoints(Polyhedron)" -- see interiorLatticePoints -- computes the lattice points in the relative interior of a polytope
• "interiorPoint(Polyhedron)" -- see interiorPoint -- computes a point in the relative interior of the Polyhedron
• "intersection(Cone,Polyhedron)" -- see intersection -- computes the intersection of half-spaces, hyperplanes, cones, and polyhedra
• "intersection(Polyhedron,Cone)" -- see intersection -- computes the intersection of half-spaces, hyperplanes, cones, and polyhedra
• "intersection(Polyhedron,Polyhedron)" -- see intersection -- computes the intersection of half-spaces, hyperplanes, cones, and polyhedra
• "isCompact(Polyhedron)" -- see isCompact -- checks compactness of a Polyhedron
• "isEmpty(Polyhedron)" -- see isEmpty -- checks if a Polyhedron is empty
• "isFace(Polyhedron,Polyhedron)" -- see isFace -- tests if the first argument is a face of the second
• "isLatticePolytope(Polyhedron)" -- see isLatticePolytope -- checks if a polyhedron is a lattice polytope
• isNormal(Polyhedron) -- checks if a polytope is normal in the ambient lattice
• "isReflexive(Polyhedron)" -- see isReflexive -- checks if a Polytope is reflexive
• "isVeryAmple(Polyhedron)" -- see isVeryAmple -- checks if the Polyhedron is very ample
• "latticePoints(Polyhedron)" -- see latticePoints -- computes the lattice points of a polytope
• "linSpace(Polyhedron)" -- see linSpace -- computes a basis of the lineality space
• "maxFace(Matrix,Polyhedron)" -- see maxFace -- computes the face of a Polyhedron or Cone where a weight attains its maximum
• "minFace(Matrix,Polyhedron)" -- see minFace -- computes the face of a Polyhedron or Cone where a weight attains its minimum
• "minkowskiSum(Cone,Polyhedron)" -- see minkowskiSum -- computes the Minkowski sum of two convex objects
• "minkowskiSum(Polyhedron,Cone)" -- see minkowskiSum -- computes the Minkowski sum of two convex objects
• "minkowskiSum(Polyhedron,Polyhedron)" -- see minkowskiSum -- computes the Minkowski sum of two convex objects
• "minkSummandCone(Polyhedron)" -- see minkSummandCone -- computes the Cone of all Minkowski summands and the minimal decompositions
• net(Polyhedron) -- displays characteristics of a polyhedron
• normalCone(Polyhedron,Polyhedron) -- computes the normal cone of a face of a polyhedron
• "normalFan(Polyhedron)" -- see normalFan -- computes the normalFan of a polyhedron
• "objectiveVector(Polyhedron,Polyhedron)" -- see objectiveVector -- computes an objective vector of a face of a polyhedron
• "polar(Polyhedron)" -- see polar -- computes the polar of a polyhedron
• "polarFace(Polyhedron)" -- see polarFace -- computes the dual face of the polar polyhedron
• "polyhedralComplex(Polyhedron)" -- see polyhedralComplex -- generates a PolyhedralComplex
• Polyhedron * Cone -- computes the direct product of a polyhedron and a cone
• Polyhedron * Polyhedron -- computes the direct product of two polyhedra
• Polyhedron + Cone -- computes the Minkowski sum of a polyhedron and a cone
• Polyhedron + Polyhedron -- computes the Minkowski sum of two polyhedra
• Polyhedron == Polyhedron -- equality
• "posHull(Polyhedron)" -- see posHull -- computes the positive hull of rays, cones, and the cone over a polyhedron
• "proximum(Matrix,Polyhedron)" -- see proximum -- computes the proximum of the Polyhedron/Cone to a point in euclidian metric
• "pyramid(Polyhedron)" -- see pyramid -- computes the pyramid over a polyhedron
• QQ * Polyhedron -- rescales a polyhedron by a given positive factor
• "ZZ * Polyhedron" -- see QQ * Polyhedron -- rescales a polyhedron by a given positive factor
• "rays(Polyhedron)" -- see rays -- displays all rays of a Cone, a Fan, or a Polyhedron
• "secondaryPolytope(Polyhedron)" -- see secondaryPolytope -- computes the secondary polytope of a compact polyhedron
• "smallestFace(Matrix,Polyhedron)" -- see smallestFace -- determines the smallest face of the Cone/Polyhedron containing a point
• "sublatticeBasis(Polyhedron)" -- see sublatticeBasis -- computes a basis for the sublattice generated by integral vectors or the lattice points of a polytope
• "tailCone(Polyhedron)" -- see tailCone -- computes the tail/recession cone of a polyhedron
• "toSublattice(Polyhedron)" -- see toSublattice -- calculates the preimage of a polytope in the sublattice generated by its lattice points
• "triangulate(Polyhedron)" -- see triangulate -- computes a triangulation of a polytope
• "vertexEdgeMatrix(Polyhedron)" -- see vertexEdgeMatrix -- computes the vertex-edge-relations matrix
• "vertexFacetMatrix(Polyhedron)" -- see vertexFacetMatrix -- computes the vertex-facet-relations matrix
• "vertices(Polyhedron)" -- see vertices -- displays the vertices of a Polyhedron or a PolyhedralComplex
• "volume(Polyhedron)" -- see volume -- computes the volume of a polytope

## For the programmer

The object Polyhedron is a type, with ancestor classes PolyhedralObject < HashTable < Thing.