GAP (CddInterface) - Chapter 2: Creating polyhedra and their Operations

‣ Cdd_PolyhedronByInequalities( ineq[, linearities_list] ) ( function )

The function takes a list in which every entry represents an inequality (or equality). In case we want some entries to represent equalities we should refer in a second list to their indices.

gap> A:= Cdd_PolyhedronByInequalities( [ [ 0, 1, 0 ], [ 0, 1, -1 ] ] );
<Polyhedron given by its H-representation>
gap> Display( A );
H-representation
begin
   2 X 3  rational

   0   1   0
   0   1  -1
end
gap> B:= Cdd_PolyhedronByInequalities( [ [ 0, 1, 0 ], [ 0, 1, -1 ] ], [ 2 ] );
<Polyhedron given by its H-representation>
gap> Display( B );
H-representation
linearity 1, [ 2 ]
begin
   2 X 3  rational

   0   1   0
   0   1  -1
end

2.1-2 Cdd_PolyhedronByGenerators

‣ Cdd_PolyhedronByGenerators( genes[, linearities_list] ) ( function )

The function takes a list in which every entry represents a vertex in the ambient vector space. In case we want some vertices to be free (the vertex and its negative belong to the polyhedron) we should refer in a second list to their indices .

gap> A:= Cdd_PolyhedronByGenerators( [ [ 0, 1, 3 ], [ 1, 4, 5 ] ] );
<Polyhedron given by its V-representation>
gap> Display( A );
V-representation
begin
   2 X 3  rational

   0  1  3
   1  4  5
end
gap> B:= Cdd_PolyhedronByGenerators( [ [ 0, 1, 3 ] ], [ 1 ] );
<Polyhedron given by its V-representation>
gap> Display( B );
V-representation
linearity 1, [ 1 ]
begin
   1 X 3  rational

   0  1  3
end

2.2 Some operations on a polyhedron

2.2-1 Cdd_FourierProjection

The function returns the Fourier projection of the polyhedron in the subspace (O,x_1,\dots,x_{i-1},x_{i+1},\dots,x_n) after applying the Fourier elemination algorithm to get rid of the variable x_{i}.

To illustrate this projection, Let P= \mathrm{conv}( (1,2), (4,5) ) in \mathbb{Q}^2. \newline To find its projection on the subspace (O, x_1), we apply the Fourier elemination to get rid of x_2

gap> P := Cdd_PolyhedronByGenerators( [ [ 1, 1, 2 ], [ 1, 4, 5 ] ] );
<Polyhedron given by its V-representation>
gap> H := Cdd_H_Rep( P );
<Polyhedron given by its H-representation>
gap> Display( H );
H-representation
linearity 1, [ 3 ]
begin
   3 X 3  rational

    4  -1   0 
   -1   1   0 
   -1  -1   1 
end
gap> P_x1 := Cdd_FourierProjection( H, 2);
<Polyhedron given by its H-representation>
gap> Display( P_x1 );
H-representation
linearity 1, [ 3 ]
begin
   3 X 3  rational

    4  -1   0
   -1   1   0
    0   0   1
end
gap> Display( Cdd_V_Rep( P_x1 ) );
V-representation
begin
   2 X 3  rational

   1  1  0
   1  4  0
end

Let again Q= Conv( (2,3,4), (2,4,5) )+ nonneg( (1,1,1) ), and let us compute its projection on (O,x_2,x_3)

gap> Q := Cdd_PolyhedronByGenerators( [ [ 1, 2, 3, 4 ],[ 1, 2, 4, 5 ], [ 0, 1, 1, 1 ] ] );
<Polyhedron given by its V-representation>
gap> R := Cdd_H_Rep( Q );
<Polyhedron given by its H-representation>
gap> Display( R );
H-representation
linearity 1, [ 4 ]
begin
   4 X 4  rational

    2   1  -1   0 
   -2   1   0   0 
   -1  -1   1   0 
   -1   0  -1   1 
end
gap> P_x2_x3 := Cdd_FourierProjection( R, 1);
<Polyhedron given by its H-representation>
gap> Display( P_x2_x3 );
H-representation
linearity 2, [ 1, 3 ]
begin
   3 X 4  rational

   -1   0  -1   1 
   -3   0   1   0 
    0   1   0   0 
end
gap> Display( Cdd_V_Rep( last ) ) ;
V-representation 
begin
   2 X 4  rational
               
   0  0  1  1 
   1  0  3  4 
end

2.3 Some operations on two polyhedrons

2.3-1 Cdd_IsContained

The function returns true if P_1 is contained in P_2, otherwise returns false.

gap> A := Cdd_PolyhedronByInequalities( [ [ 10, -1, 1, 0 ],
> [ -24, 9, 2, 0 ], [ 1, 1, -1, 0 ], [ -23, -12, 1, 11 ] ], [ 4 ] );
<Polyhedron given by its H-representation>
gap> B := Cdd_PolyhedronByInequalities( [ [ 1, 0, 0, 0 ],
> [ -4, 1, 0, 0 ], [ 10, -1, 1, 0 ], [ -3, -1, 0, 1 ] ], [ 3, 4 ] );
<Polyhedron given by its H-representation>
gap> Cdd_IsContained( B, A );
true
gap> Display( Cdd_V_Rep( A ) );
V-representation
begin
   3 X 4  rational

   1   2   3   4
   1   4  -6   7
   0   1   1   1
end
gap> Display( Cdd_V_Rep( B ) );
V-representation
begin
   2 X 4  rational

   1   4  -6   7
   0   1   1   1
end

2.3-2 Cdd_Intersection

gap> A := Cdd_PolyhedronByInequalities( [ [ 3, 4, 5 ] ], [ 1 ] );;
gap> B := Cdd_PolyhedronByInequalities( [ [ 9, 7, 2 ] ], [ 1 ] );;
gap> C := Cdd_Intersection( A, B );;
gap> Display( Cdd_V_Rep( A ) );
V-representation
linearity 1, [ 2 ]
begin
   2 X 3  rational

   1  -3/4     0
   0    -5     4
end
gap> Display( Cdd_V_Rep( B ) );
V-representation
linearity 1, [ 2 ]
begin
   2 X 3  rational

   1  -9/7     0
   0    -2     7
end
gap> Display( Cdd_V_Rep( C ) );
V-representation
begin
   1 X 3  rational

   1  -13/9    5/9
end

2.3-3 \+

gap> P := Cdd_PolyhedronByGenerators( [ [ 1, 2, 5 ], [ 0, 1, 2 ] ] );
< Polyhedron given by its V-representation >
gap> Q := Cdd_PolyhedronByGenerators( [ [ 1, 4, 6 ], [ 1, 3, 7 ], [ 0, 3, 1 ] ] );
< Polyhedron given by its V-representation >
gap> S := P+Q;
< Polyhedron given by its H-representation >
gap> V := Cdd_V_Rep( S );
< Polyhedron given by its V-representation >
gap> Display( V );
V-representation 
begin
   4 X 3  rational

   0   3   1 
   1   6  11 
   1   5  12 
   0   1   2 
end
gap> Cdd_GeneratingVertices( P ); 
[ [ 2, 5 ] ]
gap> Cdd_GeneratingVertices( Q );
[ [ 3, 7 ], [ 4, 6 ] ]
gap> Cdd_GeneratingVertices( S );
[ [ 5, 12 ], [ 6, 11 ] ]
gap> Cdd_GeneratingRays( P );
[ [ 1, 2 ] ]
gap> Cdd_GeneratingRays( Q );
[ [ 3, 1 ] ]
gap> Cdd_GeneratingRays( S );
[ [ 1, 2 ], [ 3, 1 ] ]

2 Creating polyhedra and their Operations

2.1 Creating a polyhedron