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

Working with cones

We start with a cone in 2-space which is the positive hull (coneFromVData) 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 = coneFromVData R

o2 = C

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 = coneFromVData(R1,LS)

o8 = C1

o8 : Cone
i9 : rays C1

o9 = | 0  0  |
     | -1 1  |
     | -2 -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 : hyperplanesTmp = matrix {{1,1,1}}

o11 = | 1 1 1 |

               1        3
o11 : Matrix ZZ  <--- ZZ
i12 : C2 = intersection(HS,hyperplanesTmp)
Warning: This method is deprecated. Please consider using coneFromHData instead.

o12 = C2

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
Warning: This method is deprecated. Please consider using coneFromHData instead.

o14 = C3

o14 : Cone
i15 : rays C3

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

               3        2
o15 : Matrix ZZ  <--- ZZ
i16 : linealitySpace 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 = C4

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 = C5

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 coneFromVData:

i21 : C6 = coneFromVData(C1,C2)

o21 = C6

o21 : Cone
i22 : rays C6

o22 = | 0 0  |
      | 1 -1 |
      | 0 -1 |

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

o23 = | 1 |
      | 1 |
      | 1 |

               3        1
o23 : Matrix ZZ  <--- ZZ

Furthermore, both functions (intersection 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:

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

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

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

o25 = C7

o25 : Cone
i26 : rays C7

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

               3        2
o26 : Matrix ZZ  <--- ZZ
i27 : linealitySpace 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 = P

o29 : Polyhedron
i30 : P1 = C6 + P

o30 = P1

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

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

o31 : Sequence

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

i32 : C8 = C * C1
Warning: This method is deprecated. Please consider using coneFromHData instead.

o32 = C8

o32 : Cone
i33 : rays C8

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

               5        4
o33 : Matrix ZZ  <--- ZZ
i34 : linealitySpace 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 = {{0, 2, 3}, {1, 2, 3}, {0, 1, 2}, {0, 1, 3}}

o37 : List
i38 : raysC8 = rays C8

o38 = | 2 1 0  0  |
      | 1 2 0  0  |
      | 0 0 0  0  |
      | 0 0 -1 1  |
      | 0 0 -2 -1 |

               5        4
o38 : Matrix ZZ  <--- ZZ
i39 : apply(L, l -> raysC8_l)

o39 = {| 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 |

o39 : List

We can also check if the cone is smooth:

i40 : isSmooth C8

o40 = 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.

i41 : C9 = dualCone C8

o41 = C9

o41 : Cone
i42 : rays C9

o42 = | -1 2  0  0  |
      | 2  -1 0  0  |
      | 0  0  -1 2  |
      | 0  0  2  -1 |
      | 0  0  -1 -1 |

               5        4
o42 : Matrix ZZ  <--- ZZ