Macaulay2 » Documentation
Packages » Polyhedra :: Working with polyhedra
next | previous | forward | backward | up | index | toc

# Working with polyhedra

Just like cones, polyhedra have two descriptions. One description as the convex hull of finitely many points (and optionally rays and lineality), the V-representation. Another description as the intersection of finitely many half-spaces, the H-representation. Using the method convexHull we can create a polyhedron in 2-space which is the convexHull of a given set of points.

    i1 : V = matrix {{0,2,-2,0},{-1,1,1,1}}

    o1 = | 0  2 -2 0 |
         | -1 1 1  1 |

                  2       4
    o1 : Matrix ZZ  <-- ZZ

    i2 : P = convexHull V

    o2 = P

    o2 : Polyhedron

Polyhedra uses the principle of lazy evaluation: Properties of the combinatorial objects are only computed on demand and then they are stored with the object. For example we can ask for the vertices of P using vertices:

    i3 : vertices P

    o3 = | 0  -2 2 |
         | -1 1  1 |

                  2       3
    o3 : Matrix QQ  <-- QQ

Here we see that the point (0,1) is not a vertex and P is actually a triangle.

    i4 : (HS,v) = facets P

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

    o4 : Sequence

This gives the defining affine half-spaces, i.e. P is given by all p such that HS*p <= v and that lie in the defining affine hyperplanes. The rows of the matrix HS are the outer normals of the polyhedron P. To get the defining hyperplanes we use:

    i5 : hyperplanes P

    o5 = (0, 0)

    o5 : Sequence

There are none, so the polyhedron is of full dimension. It is also compact, since P has no rays and the lineality space is of dimension zero.

    i6 : isFullDimensional P

    o6 = true

    i7 : ambDim P

    o7 = 2

    i8 : dim P

    o8 = 2

    i9 : rays P

    o9 = 0

                  2
    o9 : Matrix QQ  <-- 0

    i10 : linealitySpace P

    o10 = 0

                   2
    o10 : Matrix QQ  <-- 0

Internally, polyhedra are realized as cones, by embedding the polyhedron at height one and then taking the positive hull. To get at this cone, use cone. The height is the first coordinate of the rays of the cone, comparing the matrices of rays and vertices for the example one can see the correspondence:

    i11 : C = cone P

    o11 = C

    o11 : Cone

    i12 : rays C

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

                   3       3
    o12 : Matrix ZZ  <-- ZZ

    i13 : vertices P

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

                   2       3
    o13 : Matrix QQ  <-- QQ

We can also construct the convex hull of a set of points and a set of rays.

    i14 : R = matrix {{1},{0},{0}}

    o14 = | 1 |
          | 0 |
          | 0 |

                   3       1
    o14 : Matrix ZZ  <-- ZZ

    i15 : V1 = V || matrix {{1,1,1,1}}

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

                   3       4
    o15 : Matrix ZZ  <-- ZZ

    i16 : P1 = convexHull(V1,R)

    o16 = P1

    o16 : Polyhedron

    i17 : vertices P1

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

                   3       2
    o17 : Matrix QQ  <-- QQ

This polyhedron is not compact anymore and also not of full dimension.

    i18 : isCompact P1

    o18 = false

    i19 : isFullDimensional P1

    o19 = false

    i20 : rays P1

    o20 = | 1 |
          | 0 |
          | 0 |

                   3       1
    o20 : Matrix QQ  <-- QQ

    i21 : hyperplanes P1

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

    o21 : Sequence

On the other hand we can construct a polyhedron as the intersection of affine half-spaces and affine hyperplanes, given via inequalities and equations:

    i22 : inequalities = transpose (V || matrix {{-1,2,0,1}})

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

                   4       3
    o22 : Matrix ZZ  <-- ZZ

    i23 : v = matrix {{1},{1},{1},{1}}

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

                   4       1
    o23 : Matrix ZZ  <-- ZZ

    i24 : equations = matrix {{1,1,1}}

    o24 = | 1 1 1 |

                   1       3
    o24 : Matrix ZZ  <-- ZZ

    i25 : w = matrix {{3}}

    o25 = | 3 |

                   1       1
    o25 : Matrix ZZ  <-- ZZ

    i26 : P2 = polyhedronFromHData(inequalities,v,equations,w)

    o26 = P2

    o26 : Polyhedron

This is a triangle in 3-space with the following vertices.

    i27 : isFullDimensional P2

    o27 = false

    i28 : vertices P2

    o28 = | 4   4  2  |
          | 9   5  5  |
          | -10 -6 -4 |

                   3       3
    o28 : Matrix QQ  <-- QQ

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

    i29 : P3 = polyhedronFromHData(inequalities,v)

    o29 = P3

    o29 : Polyhedron

    i30 : vertices P3

    o30 = | 0 0  0  |
          | 1 1  -3 |
          | 0 -2 2  |

                   3       3
    o30 : Matrix QQ  <-- QQ

    i31 : linealitySpace P3

    o31 = | 1  |
          | 2  |
          | -2 |

                   3       1
    o31 : Matrix QQ  <-- QQ

    i32 : isFullDimensional P3

    o32 = true

Note that the vertices are given modulo the lineality space. Besides constructing polyhedra by hand, there are also some basic polyhedra implemented such as the hypercube, in this case with edge-length four.

    i33 : P4 = hypercube(3,2)

    o33 = P4

    o33 : Polyhedron

    i34 : vertices P4

    o34 = | -2 2  -2 2  -2 2  -2 2 |
          | -2 -2 2  2  -2 -2 2  2 |
          | -2 -2 -2 -2 2  2  2  2 |

                   3       8
    o34 : Matrix QQ  <-- QQ

Another on is the crossPolytope, in this case with diameter six.

    i35 : P5 = crossPolytope(3,3)

    o35 = P5

    o35 : Polyhedron

    i36 : vertices P5

    o36 = | -3 3 0  0 0  0 |
          | 0  0 -3 3 0  0 |
          | 0  0 0  0 -3 3 |

                   3       6
    o36 : Matrix QQ  <-- QQ

Furthermore the standard simplex (stdSimplex).

    i37 : P6 = stdSimplex 2

    o37 = P6

    o37 : Polyhedron

    i38 : vertices P6

    o38 = | 1 0 0 |
          | 0 1 0 |
          | 0 0 1 |

                   3       3
    o38 : Matrix QQ  <-- QQ

Now that we can construct polyhedra, we can turn to the functions that can be applied to polyhedra. First of all, we can apply the convexHull function also to a pair of polyhedra:

    i39 : P7 = convexHull(P4,P5)

    o39 = P7

    o39 : Polyhedron

    i40 : vertices P7

    o40 = | -3 3 0  0 0  -2 2  -2 2  -2 2  -2 2 0 |
          | 0  0 -3 3 0  -2 -2 2  2  -2 -2 2  2 0 |
          | 0  0 0  0 -3 -2 -2 -2 -2 2  2  2  2 3 |

                   3       14
    o40 : Matrix QQ  <-- QQ

Or we can intersect them by using intersect:

    i41 : P8 = intersection(P4,P5)

    o41 = P8

    o41 : Polyhedron

    i42 : vertices P8

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

                   3       24
    o42 : Matrix QQ  <-- QQ

Furthermore, both functions can be applied to a list containing any number of polyhedra and matrices defining vertices/rays or affine half-spaces/hyperplanes. All of these must be in the same ambient space. For example:

    i43 : P9 = convexHull {(V1,R),P2,P6}

    o43 = P9

    o43 : Polyhedron

    i44 : vertices P9

    o44 = | 4   4  2  0  -2 |
          | 9   5  5  -1 1  |
          | -10 -6 -4 1  1  |

                   3       5
    o44 : Matrix QQ  <-- QQ

Further functions are for example the Minkowski sum (minkowskiSum) of two polyhedra.

    i45 : Q = convexHull (-V)

    o45 = Q

    o45 : Polyhedron

    i46 : P10 = P + Q

    o46 = P10

    o46 : Polyhedron

    i47 : vertices P10

    o47 = | -4 4 -2 2  -2 2 |
          | 0  0 -2 -2 2  2 |

                   2       6
    o47 : Matrix QQ  <-- QQ

In the other direction, we can also determine all Minkowski summands (see minkSummandCone) of a polyhedron.

    i48 : (C,L,M) = minkSummandCone P10

    o48 = (C, HashTable{0 => Polyhedron{...1...}}, | 1 0 |)
                        1 => Polyhedron{...1...}   | 0 1 |
                        2 => Polyhedron{...1...}   | 1 0 |
                        3 => Polyhedron{...1...}   | 1 0 |
                        4 => Polyhedron{...1...}   | 0 1 |

    o48 : Sequence

    i49 : apply(values L, vertices)

    o49 = {| 0 4 |, | 0 4 2  |, | 0 2 |, | 0 2  |, | 0 4 2 |}
           | 0 0 |  | 0 0 -2 |  | 0 2 |  | 0 -2 |  | 0 0 2 |

    o49 : List

Here the polyhedra in the hash table L are all possible Minkowski summands up to scalar multiplication and the columns of M give the minimal decompositions. So the hexagon P10 is not only the sum of two triangles but also the sum of three lines. Furthermore, we can take the direct product of two polyhedra.

    i50 : P11 = P * Q

    o50 = P11

    o50 : Polyhedron

    i51 : vertices P11

    o51 = | 0  -2 2  0  -2 2  0  -2 2 |
          | -1 1  1  -1 1  1  -1 1  1 |
          | -2 -2 -2 2  2  2  0  0  0 |
          | -1 -1 -1 -1 -1 -1 1  1  1 |

                   4       9
    o51 : Matrix QQ  <-- QQ

The result is in QQ^4.

    i52 : ambDim P11

    o52 = 4

To find out more about this polyhedron use for example.

    i53 : fVector P11

    o53 = {9, 18, 15, 6, 1}

    o53 : List

The function fVector gives the number of faces of each dimension, so it has 9 vertices, 18 edges and so on. We can access the faces of a certain codimension via:

    i54 : L = faces(1,P11)

    o54 = {({0, 1, 3, 4, 6, 7}, {}), ({0, 2, 3, 5, 6, 8}, {}), ({1, 2, 4, 5, 7,
          -----------------------------------------------------------------------
          8}, {}), ({0, 1, 2, 3, 4, 5}, {}), ({0, 1, 2, 6, 7, 8}, {}), ({3, 4, 5,
          -----------------------------------------------------------------------
          6, 7, 8}, {})}

    o54 : List

    i55 : vertP11 = vertices P11

    o55 = | 0  -2 2  0  -2 2  0  -2 2 |
          | -1 1  1  -1 1  1  -1 1  1 |
          | -2 -2 -2 2  2  2  0  0  0 |
          | -1 -1 -1 -1 -1 -1 1  1  1 |

                   4       9
    o55 : Matrix QQ  <-- QQ

    i56 : apply(L, l -> vertP11_(l#0))

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

    o56 : List

We can compute all lattice points of the polyhedron with latticePoints.

    i57 : L = latticePoints P11

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

    o57 : List

    i58 : #L

    o58 = 81

Evenmore the tail/recession cone of a polyhedron with tailCone.

    i59 : C = tailCone P1

    o59 = C

    o59 : Cone

    i60 : rays C

    o60 = | 1 |
          | 0 |
          | 0 |

                   3       1
    o60 : Matrix ZZ  <-- ZZ

Finally, there is also a function to compute the polar of a polyhedron, i.e. all points in the dual space that are greater than -1 on all points of the polyhedron:

    i61 : P12 = polar P11

    o61 = P12

    o61 : Polyhedron

    i62 : vertices P12

    o62 = | 1 -1 0  0 0  0  |
          | 1 1  -1 0 0  0  |
          | 0 0  0  0 1  -1 |
          | 0 0  0  1 -1 -1 |

                   4       6
    o62 : Matrix QQ  <-- QQ

The source of this document is in /build/macaulay2-88fgJW/macaulay2-1.25.11+ds/M2/Macaulay2/packages/Polyhedra/documentation/working_with_polyhedra.m2:239:0.