next | previous | forward | backward | up | top | index | toc | Macaulay2 website
OldPolyhedra :: Working with cones

Working with cones

We start with a cone in 2-space which is the positive hull (posHull) of a given set of rays.
i1 : R = matrix {{1,1,2},{2,1,1}}

o1 = | 1 1 2 |
     | 2 1 1 |

              2        3
o1 : Matrix ZZ  <--- ZZ
i2 : C = posHull R

o2 = {ambient dimension => 2           }
      dimension of lineality space => 0
      dimension of the cone => 2
      number of facets => 2
      number of rays => 2

o2 : Cone
i3 : ambDim C

o3 = 2

This gives an overview of the characteristics of the cone. If we want to know more details, we can ask for them.

i4 : rays C

o4 = | 2 1 |
     | 1 2 |

              2        2
o4 : Matrix ZZ  <--- ZZ

Using rays we see that (1,1) is not an extremal ray of the cone.

i5 : HS = halfspaces C

o5 = | -1 2  |
     | 2  -1 |

              2        2
o5 : Matrix ZZ  <--- ZZ

The function halfspaces gives the defining linear half-spaces, i.e. C is given by all p in the defining linear hyperplanes that satisfy HS*p >= 0. But in this case there are none, so the polyhedron is of full dimension. Furthermore, we can construct the positive hull of a set of rays and a linear subspace.

i6 : R1 = R || matrix {{0,0,0}}

o6 = | 1 1 2 |
     | 2 1 1 |
     | 0 0 0 |

              3        3
o6 : Matrix ZZ  <--- ZZ
i7 : LS = matrix {{1},{1},{1}}

o7 = | 1 |
     | 1 |
     | 1 |

              3        1
o7 : Matrix ZZ  <--- ZZ
i8 : C1 = posHull(R1,LS)

o8 = {ambient dimension => 3           }
      dimension of lineality space => 1
      dimension of the cone => 3
      number of facets => 2
      number of rays => 2

o8 : Cone
i9 : rays C1

o9 = | 1  0  |
     | 0  1  |
     | -1 -1 |

              3        2
o9 : Matrix ZZ  <--- ZZ

Note that the rays are given modulo the lineality space. On the other hand we can construct cones as the intersection of linear half-spaces and hyperplanes.

i10 : HS = transpose R1

o10 = | 1 2 0 |
      | 1 1 0 |
      | 2 1 0 |

               3        3
o10 : Matrix ZZ  <--- ZZ
i11 : HP = matrix {{1,1,1}}

o11 = | 1 1 1 |

               1        3
o11 : Matrix ZZ  <--- ZZ
i12 : C2 = intersection(HS,HP)

o12 = {ambient dimension => 3           }
       dimension of lineality space => 0
       dimension of the cone => 2
       number of facets => 2
       number of rays => 2

o12 : Cone

This is a two dimensional cone in 3-space with the following rays:

i13 : rays C2

o13 = | 2  -1 |
      | -1 2  |
      | -1 -1 |

               3        2
o13 : Matrix ZZ  <--- ZZ

If we don't intersect with the hyperplane we get a full dimensional cone.

i14 : C3 = intersection HS

o14 = {ambient dimension => 3           }
       dimension of lineality space => 1
       dimension of the cone => 3
       number of facets => 2
       number of rays => 2

o14 : Cone
i15 : rays C3

o15 = | 2  -1 |
      | -1 2  |
      | 0  0  |

               3        2
o15 : Matrix ZZ  <--- ZZ
i16 : linSpace C3

o16 = | 0 |
      | 0 |
      | 1 |

               3        1
o16 : Matrix ZZ  <--- ZZ

Again, the rays are given modulo the lineality space. Also, one can use given cones, for example the positive orthant (posOrthant):

i17 : C4 = posOrthant 3

o17 = {ambient dimension => 3           }
       dimension of lineality space => 0
       dimension of the cone => 3
       number of facets => 3
       number of rays => 3

o17 : Cone
i18 : rays C4

o18 = | 1 0 0 |
      | 0 1 0 |
      | 0 0 1 |

               3        3
o18 : Matrix ZZ  <--- ZZ

Now that we can construct cones, we can turn to the functions that can be applied to cones. First of all, we can apply the intersection function also to a pair of cones in the same ambient space:

i19 : C5 = intersection(C1,C2)

o19 = {ambient dimension => 3           }
       dimension of lineality space => 0
       dimension of the cone => 2
       number of facets => 2
       number of rays => 2

o19 : Cone
i20 : rays C5

o20 = | 1  0  |
      | 0  1  |
      | -1 -1 |

               3        2
o20 : Matrix ZZ  <--- ZZ

On the other hand, we can take their positive hull by using posHull:

i21 : C6 = posHull(C1,C2)

o21 = {ambient dimension => 3           }
       dimension of lineality space => 1
       dimension of the cone => 3
       number of facets => 2
       number of rays => 2

o21 : Cone
i22 : rays C6

o22 = | 2  -1 |
      | -1 2  |
      | -1 -1 |

               3        2
o22 : Matrix ZZ  <--- ZZ
i23 : linSpace C6

o23 = | 1 |
      | 1 |
      | 1 |

               3        1
o23 : Matrix ZZ  <--- ZZ

Furthermore, both functions (intersection and posHull) can be applied to a list containing any number of cones and matrices defining rays and lineality space or linear half-spaces and hyperplanes. These must be in the same ambient space. For example:

i24 : R2 = matrix {{2,-1},{-1,2},{-1,-1}}

o24 = | 2  -1 |
      | -1 2  |
      | -1 -1 |

               3        2
o24 : Matrix ZZ  <--- ZZ
i25 : C7 = posHull {R2,C3,C4}

o25 = {ambient dimension => 3           }
       dimension of lineality space => 1
       dimension of the cone => 3
       number of facets => 2
       number of rays => 2

o25 : Cone
i26 : rays C7

o26 = | 2  -1 |
      | -1 2  |
      | 0  0  |

               3        2
o26 : Matrix ZZ  <--- ZZ
i27 : linSpace C7

o27 = | 0 |
      | 0 |
      | 1 |

               3        1
o27 : Matrix ZZ  <--- ZZ

Since they are all cones their positive hull is the same as their Minkowski sum, so in fact:

i28 : C6 == C1 + C2

o28 = true

But we can take the Minkowski sum of a cone and a polyhedron. For this, both objects must lie in the same ambient space and the resulting object is then a polyhedron:

i29 : P = crossPolytope 3

o29 = {ambient dimension => 3           }
       dimension of lineality space => 0
       dimension of polyhedron => 3
       number of facets => 8
       number of rays => 0
       number of vertices => 6

o29 : Polyhedron
i30 : P1 = C6 + P

o30 = {ambient dimension => 3           }
       dimension of lineality space => 1
       dimension of polyhedron => 3
       number of facets => 2
       number of rays => 2
       number of vertices => 1

o30 : Polyhedron
i31 : (vertices P1,rays P1)

o31 = (| -1/3 |, | 2  -1 |)
       | -1/3 |  | -1 2  |
       | 2/3  |  | -1 -1 |

o31 : Sequence

Furthermore, we can take the direct product (directProduct) of two cones.

i32 : C8 = C * C1

o32 = {ambient dimension => 5           }
       dimension of lineality space => 1
       dimension of the cone => 5
       number of facets => 4
       number of rays => 4

o32 : Cone
i33 : rays C8

o33 = | 2 1 0  0  |
      | 1 2 0  0  |
      | 0 0 1  0  |
      | 0 0 0  1  |
      | 0 0 -1 -1 |

               5        4
o33 : Matrix ZZ  <--- ZZ
i34 : linSpace C8

o34 = | 0 |
      | 0 |
      | 1 |
      | 1 |
      | 1 |

               5        1
o34 : Matrix ZZ  <--- ZZ

The result is in QQ^5.

i35 : ambDim C8

o35 = 5

To find out more about this cone use for example fVector:

i36 : fVector C8

o36 = {0, 1, 4, 6, 4, 1}

o36 : List

This function gives the number of faces of each dimension, so it has 1 vertex, the origin, 1 line, 4 two dimensional faces and so on. We can access the faces of a certain codimension via faces:

i37 : L = faces(1,C8)

o37 = {{ambient dimension => 5           }, {ambient dimension => 5         
        dimension of lineality space => 1    dimension of lineality space =>
        dimension of the cone => 4           dimension of the cone => 4     
        number of facets => 3                number of facets => 3          
        number of rays => 3                  number of rays => 3            
      -----------------------------------------------------------------------
       }, {ambient dimension => 5           }, {ambient dimension => 5      
      1    dimension of lineality space => 1    dimension of lineality space
           dimension of the cone => 4           dimension of the cone => 4
           number of facets => 3                number of facets => 3
           number of rays => 3                  number of rays => 3
      -----------------------------------------------------------------------
          }}
      => 1

o37 : List
i38 : apply(L,rays)

o38 = {| 2 0  0  |, | 1 0  0  |, | 2 1 0  |, | 2 1 0  |}
       | 1 0  0  |  | 2 0  0  |  | 1 2 0  |  | 1 2 0  |
       | 0 1  0  |  | 0 1  0  |  | 0 0 1  |  | 0 0 0  |
       | 0 0  1  |  | 0 0  1  |  | 0 0 0  |  | 0 0 1  |
       | 0 -1 -1 |  | 0 -1 -1 |  | 0 0 -1 |  | 0 0 -1 |

o38 : List

We can also check if the cone is smooth:

i39 : isSmooth C8

o39 = false

Evenmore we can compute the Hilbert basis of the cone with hilbertBasis.

i40 : L = hilbertBasis C8

o40 = {| 0 |, | 0 |, | 0 |, | -1 |, | 0  |, | -1 |}
       | 0 |  | 0 |  | 0 |  | -1 |  | -1 |  | 0  |
       | 0 |  | 0 |  | 0 |  | -2 |  | -2 |  | -2 |
       | 1 |  | 2 |  | 1 |  | 0  |  | 0  |  | 0  |
       | 1 |  | 1 |  | 2 |  | 0  |  | 0  |  | 0  |

o40 : List
i41 : #L

o41 = 6

Finally, there is also a function to compute the dual cone, i.e. the set of all points in the dual space that are positive on the cone.

i42 : C9 = dualCone C8

o42 = {ambient dimension => 5           }
       dimension of lineality space => 0
       dimension of the cone => 4
       number of facets => 4
       number of rays => 4

o42 : Cone
i43 : rays C9

o43 = | 2  -1 0  0  |
      | -1 2  0  0  |
      | 0  0  2  -1 |
      | 0  0  -1 2  |
      | 0  0  -1 -1 |

               5        4
o43 : Matrix ZZ  <--- ZZ