Educational Materials

Vertex Enumeration Package for Convex Polytopes and Arrangements, Version 0.41 Beta

Komei Fukuda, Ichiro Mizukoshi

Author

Komei Fukuda, Ichiro Mizukoshi

Title

Vertex Enumeration Package for Convex Polytopes and Arrangements, Version 0.41 Beta

Description

The package 'VertexEnumeration' contains Mathematica implementations of Avis-Fukuda algorithms for enumerating all vertices of a convex polytope given by a system of linear inequalities, and for enumerating all points (0-dimensional faces) of an arrangement of hyperplanes given similarly. The package also generates Voronoi diagrams and graphs. The supplementary package 'FaceLattice.m' computes the face lattice structure of a bounded convex polyhedron.

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]

All 0-faces determined.
All 1-faces determined.
All 2-faces determined.
All 3-faces determined.
All 4-faces determined.

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

FaceLatticeDiagram FVector KFaceList
FaceLatticeLinks

Cite this as: Komei Fukuda, Ichiro Mizukoshi, "Vertex Enumeration Package for Convex Polytopes and Arrangements, Version 0.41 Beta" from the Notebook Archive (2003), https://notebookarchive.org/2018-10-10qc4dn

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)

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)