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

Working with cones

Every cone can be described via generating rays or via inequalities. The description via rays (or vertices for polyhedra) is often referred to as the V-representation. The description via inequalities is called the H-representation. To create a cone in 2-space which is the positive hull of a given set of rays use coneFromVData:

i1 : R = matrix {{1,1,2},{2,1,1}}

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

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

o2 = C

o2 : Cone
i3 : ambDim C

o3 = 2

After creating the cone, one can use rays to ask for its minimal rays.

i4 : rays C

o4 = | 2 1 |
     | 1 2 |

              2        2
o4 : Matrix ZZ  <--- ZZ

We see that (1,1) is not an extremal ray of the cone.

i5 : HS = facets C

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

              2        2
o5 : Matrix ZZ  <--- ZZ
i6 : hyperplanes C

o6 = 0

                     2
o6 : Matrix 0 <--- ZZ
i7 : isFullDimensional C

o7 = true

The function facets gives the defining linear half-spaces, the H-representation, i.e. C is given by all p in the defining linear hyperplanes that satisfy HS*p >= 0. In this case there are no hyperplanes, so the cone is of full dimension. The rows of the matrix HS are the inner normals of the cone. Furthermore, we can construct the positive hull of a set of rays and a linear subspace.

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

o8 = | 1 1 2 |
     | 2 1 1 |
     | 0 0 0 |

              3        3
o8 : Matrix ZZ  <--- ZZ
i9 : LS = matrix {{1},{1},{1}}

o9 = | 1 |
     | 1 |
     | 1 |

              3        1
o9 : Matrix ZZ  <--- ZZ
i10 : C1 = coneFromVData(R1,LS)

o10 = C1

o10 : Cone
i11 : rays C1

o11 = | 0  0  |
      | -1 1  |
      | -2 -1 |

               3        2
o11 : 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. The first argument of coneFromHData takes the inequalities defining the cone, while the second takes equations.

i12 : HS = transpose R1

o12 = | 1 2 0 |
      | 1 1 0 |
      | 2 1 0 |

               3        3
o12 : Matrix ZZ  <--- ZZ
i13 : equations = matrix {{1,1,1}}

o13 = | 1 1 1 |

               1        3
o13 : Matrix ZZ  <--- ZZ
i14 : C2 = coneFromHData(HS,equations)

o14 = C2

o14 : Cone
i15 : dim C2

o15 = 2
i16 : ambDim C2

o16 = 3

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

i17 : rays C2

o17 = | 2  -1 |
      | -1 2  |
      | -1 -1 |

               3        2
o17 : Matrix ZZ  <--- ZZ

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

i18 : C3 = coneFromHData HS

o18 = C3

o18 : Cone
i19 : rays C3

o19 = | 2  -1 |
      | -1 2  |
      | 0  0  |

               3        2
o19 : Matrix ZZ  <--- ZZ
i20 : linealitySpace C3

o20 = | 0 |
      | 0 |
      | 1 |

               3        1
o20 : Matrix ZZ  <--- ZZ
i21 : isFullDimensional C3

o21 = true

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

i22 : C4 = posOrthant 3

o22 = C4

o22 : Cone
i23 : rays C4

o23 = | 1 0 0 |
      | 0 1 0 |
      | 0 0 1 |

               3        3
o23 : 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:

i24 : C5 = intersection(C1,C2)

o24 = C5

o24 : Cone
i25 : rays C5

o25 = | 1  0  |
      | 0  1  |
      | -1 -1 |

               3        2
o25 : Matrix ZZ  <--- ZZ
i26 : dim C5

o26 = 2

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

i27 : C6 = coneFromVData(C1,C2)

o27 = C6

o27 : Cone
i28 : rays C6

o28 = | 0 0  |
      | 1 -1 |
      | 0 -1 |

               3        2
o28 : Matrix ZZ  <--- ZZ
i29 : linealitySpace C6

o29 = | 1 |
      | 1 |
      | 1 |

               3        1
o29 : Matrix ZZ  <--- ZZ

Furthermore, both functions (coneFromHData and coneFromVData) 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:

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

o30 = | 2  -1 |
      | -1 2  |
      | -1 -1 |

               3        2
o30 : Matrix ZZ  <--- ZZ
i31 : C7 = coneFromVData {R2,C3,C4}

o31 = C7

o31 : Cone
i32 : rays C7

o32 = | 2  -1 |
      | -1 2  |
      | 0  0  |

               3        2
o32 : Matrix ZZ  <--- ZZ
i33 : linealitySpace C7

o33 = | 0 |
      | 0 |
      | 1 |

               3        1
o33 : Matrix ZZ  <--- ZZ

Taking the positive hull of several cones is the same as taking their Minkowski sum, so in fact:

i34 : C6 == C1 + C2

o34 = true

We can also 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:

i35 : P = crossPolytope 3

o35 = P

o35 : Polyhedron
i36 : P1 = C6 + P

o36 = P1

o36 : Polyhedron
i37 : (vertices P1,rays P1)

o37 = (| 0 |, | 0 0  |)
       | 0 |  | 1 -1 |
       | 1 |  | 0 -1 |

o37 : Sequence

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

i38 : C8 = C * C1

o38 = C8

o38 : Cone
i39 : rays C8

o39 = | 2 1 0  0  |
      | 1 2 0  0  |
      | 0 0 0  0  |
      | 0 0 -1 1  |
      | 0 0 -2 -1 |

               5        4
o39 : Matrix ZZ  <--- ZZ
i40 : linealitySpace C8

o40 = | 0 |
      | 0 |
      | 1 |
      | 1 |
      | 1 |

               5        1
o40 : Matrix ZZ  <--- ZZ
i41 : ambDim C8

o41 = 5

The result is contained in ${\mathbb Q}^5$.

i42 : ambDim C8

o42 = 5

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

i43 : fVector C8

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

o43 : 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. The output of faces is a list of list of indices that indicate which rays form a face. The following shows how to get the corresponding rays of the faces.

i44 : L = faces(1,C8)

o44 = {{0, 2, 3}, {1, 2, 3}, {0, 1, 2}, {0, 1, 3}}

o44 : List
i45 : raysC8 = rays C8

o45 = | 2 1 0  0  |
      | 1 2 0  0  |
      | 0 0 0  0  |
      | 0 0 -1 1  |
      | 0 0 -2 -1 |

               5        4
o45 : Matrix ZZ  <--- ZZ
i46 : apply(L, l -> raysC8_l)

o46 = {| 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 0  0  |  | 0 0  0  |  | 0 0 0  |  | 0 0 0  |
       | 0 -1 1  |  | 0 -1 1  |  | 0 0 -1 |  | 0 0 1  |
       | 0 -2 -1 |  | 0 -2 -1 |  | 0 0 -2 |  | 0 0 -1 |

o46 : List

We can also check if the cone is smooth:

i47 : isSmooth C8

o47 = false

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.

i48 : C9 = dualCone C8

o48 = C9

o48 : Cone
i49 : rays C9

o49 = | -1 2  0  0  |
      | 2  -1 0  0  |
      | 0  0  -1 2  |
      | 0  0  2  -1 |
      | 0  0  -1 -1 |

               5        4
o49 : Matrix ZZ  <--- ZZ