cddmathlink
Convex Hull and Vertex Enumeration by MathLink to cddlib
by Komei Fukuda
April 17, 2001

Connecting  cddmathlink

You just put the compiled cddmathlink for your computer in some directory.  In this example, the name of the directory is "~/Math".

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

cddml=
Install["~/Math/cddmathlink"]

Generating All Vertices

?AllVertices

Let's try this function with a 3-dimenstional cube defined by 6 inequalities (facets);  
x1  >= 0, x2 >=0, x3 >= 0, 1 - x1 >= 0,   1 - x2 >= 0 and  1 - x3 >= 0.  We write these six inequalities  as   A  x  >=  0  and  x=(1, x1, x2, x3).

MatrixForm[a={{0,1,0,0},{0,0,1,0},{0,0,0,1},
	{1,-1,0,0},{1,0,-1,0},{1,0,0,-1}}]

{m,d1}=Dimensions[a]

{{vertices, linearity}, incidences}=AllVertices[m,d1,Flatten[a]]

Generating the Graph Structure

?AllVerticesWithAdjacency

{{vertices,linearity},ecd,ead,icd,iad}=
	AllVerticesWithAdjacency[m,d1,Flatten[a]]

The graph structure is output as the adjacency  list  ead. For example, the first list {2, 4 ,8} represents the neighbour vertices of the first vertex 1.  The adjacency of input is given by
the list  iad.

Convex Hull (Facet Generation)

?AllFacets

We have computed all the vertices of a 3-cube.  Let's try the reverse operation.  First check the size of the list of vertics.   It should reconstruct the facets we have started with.

{n, d1}=Dimensions[vertices]

{{facets,equalities}, fincidences}= AllFacets[n,d1,Flatten[vertices]]

We can compute how the facets are connected by using AllFacetsWithAdjacency function.

{{facets,equalities}, icd,iad, ecd,ead}= 
	AllFacetsWithAdjacency[n,d1,Flatten[vertices]]

If you want to compute an inequality description of the one-dimensional cone in R^3 with a vertex at origin and containing the direction (1,1,1), you must set up the input (generator) data as:

coneGenerators={{1,0,0,0},{0,1,1,1}}

{{cfacets,cequalities}, cfincidences}= 
	AllFacets[2,4,Flatten[coneGenerators]]

Since the equalities list contains 3 and 4, of the four output inequalities , the third and the forth must be considered as equalities.  It is important to note that this cone can have infinitely many different minimal inequality descriptions, since it is not full-dimensional.

A Larger Example (Random 0/1 Polytopes)

Let's compute the convex hull of 0/1 points in R^d.  First generate 0/1 points.  Below each point with the first component 0 is considered as a direction that must be included in the convex hull.

n=30; d1=8;

points=Table[Prepend[Table[Random[Integer,{0,1}],{d1-1}],0],{n}]

Dimensions[points]

{CPUtime, {{facets,equalities}, inc}}= 
	Timing[AllFacets[n,d1,Flatten[points]]];

{CPUtime,Length[facets]}

Usually facets of 0/1 polytopes are very pretty and their coefficients are small integers.

Take[facets,5]

Disconnecting  cddmathlink

Uninstall[cddml]