next | previous | forward | backward | up | top | index | toc | Macaulay2 website
Polyhedra :: V- and H-representation

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