Generating All Faces of Convex Polytopes:FaceLattice.m
-Mathematica  Package -
Version 0.2 Beta,  September 19, 1992

Komei Fukuda(University of Tsukuba, Tokyo) 
and 
Vera Rosta(Temple University Japan)

In this small notebook, we shall explain how to enumerate all faces of a d-dimensional convex polytope using the package FaceLattice.m which is distributed with VertexEnum package. (A convex polytope is a bounded convex polyhedron.)   Since the package FaceLattice.m  automatically reads two other packages, VertexEnum.m and Combinatorica.m, it is important that those packages are available in your computing environment before you try read in the FaceLattice package.  Combinatorica.m is a standard Mathematica package which is to be in the directory DiscreteMath.

$Path=Join[$Path, {"~/NeXT/NeXTmath/VertexEnum"}]

<<FaceLattice.m;

Off[General::spell];  Off[General::spell1];

Let us first generate randomly a system of linear inequalities: m.x <=b and x>=0 whose solution set  is a 5-dimensional convex polytope with 7 facets.

size=2;    dim=5;

m=Table[Table[Random[Integer,{1,5}],{dim}],{size}]

b=Table[Sum[m[[i,j]],{j,dim}],{i,size}]

Then we compute all vertices of the polytope using the VetexEnumeration function of  VertexEnum package.

vlist=VertexEnumeration[m,b];

activesets=vlist[[2]]

Here activesets is the list of vertices, each represented as the set of indices of inequalities which are satisfied by equality (i.e. active) at the vertex. We can represent each face of the polytope exactly the same manner.  In fact, by taking all possible intersections of members of activesets, we can generate all faces. The function KFaceList outputs {F-1,F0,F1,F2,...,Fd} where d is the dimension of the polytope and Fk is the list of k-dimensional faces for k=-1,0,1,2,...,d.

(* The following takes about two minutes on Macintosh SE/30 *)

flist=KFaceList[activesets]

The function FVector counts the number of k-faces for k=-1,0,2,...,d.

fvector=FVector[flist]

There is a well-known theorem about the f-vector:  Euler-Poincare's relation.  This relation says that the alternate sum of the number of k-faces is always zero.  We can test whether it is true for our example.  First we make the (+1,-1) alternating vector.

avector=Table[(-1)^i,{i,Length[flist]}]

The following must be true.  (If not, who is responsible for it?)

TrueQ[avector.fvector==0]

It is not easy to draw by hand the face lattice of general convex polytopes, but the function FaceLatticeDiagram automatically generates a Mathematica  graphics for it.  Whether or not the drawing is useful is a different question!

Show[FaceLatticeDiagram[flist]]

If  you want to know exactly what are the links in the diagram above, execute the function  FaceLatticeLinks.

flinks=FaceLatticeLinks[flist];
flinks //Short

Here, each element {{k,m},{k+1,n}} of flinks indicates that  the m-th face of dimension k is  covered by the n-th face of dimension k+1.

Since we have imported Combinatorica package also,  we conlude this notebook with explanation for drawing the graph of the polytope using the package:

edges=EdgesOfPolyhedron[activesets];

ShowLabeledGraph[g=FromUnorderedPairs[edges]]

?FaceLattice`*