Macaulay2 » Documentation
Packages » Polyhedra :: V- and H-representation
next | previous | forward | backward | up | index | toc

# V- and H-representation

Short summary and conventions

Both cones and polyhedra can be described either by giving generators, the so-called V-representation or by giving inequalities, the so-called H-representation. We have the following conventions:

1. Rays, vertices, and generators of the lineality space are given as columns of matrices.

2. Inequalities and hyperplanes are given as rows of matrices.

3. The inequality description of a cone is $A\cdot x\ge 0$.

4. The inequality description of a polyhedron is $A\cdot x\le b$.

Conventions for cones

For cones we have the convention that the scalar product of generators with inequalities is positive:

    i1 : C = coneFromVData matrix {{1,0,0},{1,1,0},{1,0,1},{1,1,1}}

    o1 = C

    o1 : Cone

    i2 : rays C

    o2 = | 0 0 1 |
         | 1 0 1 |
         | 0 1 1 |
         | 1 1 1 |

                  4       3
    o2 : Matrix ZZ  <-- ZZ

    i3 : facets C

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

                  3       4
    o3 : Matrix ZZ  <-- ZZ

    i4 : (facets C) * (rays C)

    o4 = | 0 1 0 |
         | 1 0 0 |
         | 0 0 1 |

                  3       3
    o4 : Matrix ZZ  <-- ZZ

The hyperplanes of a cone evaluate to zero with the rays of a cone, just like the linealitySpace evaluates to zero with the facets.

    i5 : (hyperplanes C) * (rays C)

    o5 = 0

                  1       3
    o5 : Matrix ZZ  <-- ZZ

    i6 : (facets C) * (linealitySpace C)

    o6 = 0

                  3
    o6 : Matrix ZZ  <-- 0

Conventions for polyhedra

For a polyhedron the situation is slightly different, as we have a right hand side to take into account, since we are dealing with affine hyperplanes instead of just hyperplanes.

    i7 : P = hypercube(2,0,1)

    o7 = P

    o7 : Polyhedron

    i8 : V = vertices P

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

                  2       4
    o8 : Matrix QQ  <-- QQ

    i9 : (A, b) = facets P

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

    o9 : Sequence

    i10 : A * V

    o10 = | 0 -1 0  -1 |
          | 0 1  0  1  |
          | 0 0  -1 -1 |
          | 0 0  1  1  |

                   4       4
    o10 : Matrix QQ  <-- QQ

The convention is that for any point $p$ in the polyhedron we have $A\cdot p\le b$. This means we have $0\le b - A\cdot p$. Again, this may be handled differently elsewhere.

    i11 : for i from 0 to numColumns V - 1 do (
                test := b - A*V_{i};
                << "Vertex " << i << " " << (flatten entries V_{i}) << ": " << all(flatten entries test, e -> e>= 0) << endl;
             )
    Vertex 0 {0, 0}: true
    Vertex 1 {1, 0}: true
    Vertex 2 {0, 1}: true
    Vertex 3 {1, 1}: true

From the above convention it follows that the facets evaluate negatively with the rays and linealitySpace of a polyhedron. Conversely to hyperplanes evaluate to constants on the vertices of a polyhedron.

    i12 : P = convexHull(matrix{{1,0},{0,1},{2,2}}, matrix {{1},{1},{2}})

    o12 = P

    o12 : Polyhedron

    i13 : vertices P

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

                   3       2
    o13 : Matrix QQ  <-- QQ

    i14 : rays P

    o14 = | 1 |
          | 1 |
          | 2 |

                   3       1
    o14 : Matrix QQ  <-- QQ

    i15 : (A, b) = facets P

    o15 = (| 2  0  -1 |, 0)
           | 0  2  -1 |
           | -2 -2 1  |

    o15 : Sequence

    i16 : A * (vertices P)

    o16 = | 0  -2 |
          | -2 0  |
          | 0  0  |

                   3       2
    o16 : Matrix QQ  <-- QQ

    i17 : A * (rays P)

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

                   3       1
    o17 : Matrix QQ  <-- QQ

    i18 : (E, v) = hyperplanes P

    o18 = (| 1 1 -1 |, | -1 |)

    o18 : Sequence

    i19 : E * (rays P)

    o19 = 0

                   1       1
    o19 : Matrix QQ  <-- QQ

    i20 : E * (vertices P)

    o20 = | -1 -1 |

                   1       2
    o20 : Matrix QQ  <-- QQ

Full representations

1. The pair (rays, linealitySpace) is a valid V-representation of a cone.

2. The pair (facets, hyperplanes) is a valid H-representation of a cone.

3. The triple (vertices, rays, linealitySpace) is a valid V-representation of a polyhedron.

4. The triple (facets, hyperplanes) is a valid H-representation of a polyhedron.

That means we have the following identities:

    i21 : C == coneFromVData(rays C, linealitySpace C)

    o21 = true

    i22 : C == coneFromRays(rays C, linealitySpace C)

    o22 = true

    i23 : C == coneFromHData(facets C, hyperplanes C)

    o23 = true

    i24 : C == coneFromInequalities(facets C, hyperplanes C)

    o24 = true

    i25 : P == convexHull (vertices P, rays P, linealitySpace P)

    o25 = true

    i26 : F = facets P

    o26 = (| 2  0  -1 |, 0)
           | 0  2  -1 |
           | -2 -2 1  |

    o26 : Sequence

    i27 : H = hyperplanes P

    o27 = (| 1 1 -1 |, | -1 |)

    o27 : Sequence

    i28 : P == polyhedronFromHData(F#0, F#1, H#0, H#1)

    o28 = true

    i29 : P == polyhedronFromInequalities(F#0, F#1, H#0, H#1)

    o29 = true

## See also

- coneFromVData -- computes the positive hull of rays, cones, and the cone over a polyhedron
- coneFromHData -- Constructing a polyhedral cone as intersection of halfspaces.
- convexHull -- computing the convex hull of points, rays and polyhedra
- polyhedronFromHData -- Constructing a polyhedron from its H-representation, i.e. inequalities and equations
- facets -- Giving the facet inequalities of a cone or polyhedron.
- hyperplanes -- computes the defining hyperplanes of a Cone or a Polyhedron
- linealitySpace -- computes a basis of the lineality space
- rays(PolyhedralObject) -- displays all rays of a Cone, a Fan, or a Polyhedron
- vertices -- displays the vertices of a Polyhedron or a PolyhedralComplex

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