next | previous | forward | backward | up | top | index | toc | Macaulay2 web site
Polyhedra :: Polyhedron

Polyhedron -- the class of all convex polyhedra

Description

A Polyhedron represents a rational polyhedron. It can be bounded or unbounded, need not be full dimensional or may contain a proper affine subspace. It can be empty or zero dimensional. It is saved as a hash table which contains the vertices, generating rays, and the basis of the lineality space of the Polyhedron as well as the defining affine half-spaces and hyperplanes. The output of a Polyhedron looks like this:
i1 : convexHull(matrix {{0,0,-1,-1},{2,-2,1,-1},{0,0,0,0}},matrix {{1},{0},{0}})

o1 = Polyhedron{...1...}

o1 : Polyhedron

This table displays a short summary of the properties of the Polyhedron. Note that the number of rays and vertices are modulo the lineality space. So for example a line in QQ^2 has one vertex and no rays. However, one can not access the above information directly, because this is just a virtual hash table generated for the output. The data defining a Polyhedron is extracted by the functions included in this package. A Polyhedron can be constructed as the convex hull (convexHull) of a set of points and a set of rays or as the intersection (polyhedronFromHData) of a set of affine half-spaces and affine hyperplanes.

For example, consider the square and the square with an emerging ray for the convex hull:

i2 : V = matrix {{1,1,-1,-1},{1,-1,1,-1}}

o2 = | 1 1  -1 -1 |
     | 1 -1 1  -1 |

              2        4
o2 : Matrix ZZ  <--- ZZ
i3 : convexHull V

o3 = Polyhedron{...1...}

o3 : Polyhedron
i4 : R = matrix {{1},{1}}

o4 = | 1 |
     | 1 |

              2        1
o4 : Matrix ZZ  <--- ZZ
i5 : convexHull(V,R)

o5 = Polyhedron{...1...}

o5 : Polyhedron

If we take the intersection of the half-spaces defined by the directions of the vertices and 1 we get the crosspolytope:

i6 : HS = transpose V

o6 = | 1  1  |
     | 1  -1 |
     | -1 1  |
     | -1 -1 |

              4        2
o6 : Matrix ZZ  <--- ZZ
i7 : v = R || R

o7 = | 1 |
     | 1 |
     | 1 |
     | 1 |

              4        1
o7 : Matrix ZZ  <--- ZZ
i8 : P = polyhedronFromHData(HS,v)

o8 = P

o8 : Polyhedron
i9 : vertices P

o9 = | -1 1 0  0 |
     | 0  0 -1 1 |

              2        4
o9 : Matrix QQ  <--- QQ

This can for example be embedded in 3-space on height 1:

i10 : HS = HS | matrix {{0},{0},{0},{0}}

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

               4        3
o10 : Matrix ZZ  <--- ZZ
i11 : hyperplanesTmp = matrix {{0,0,1}}

o11 = | 0 0 1 |

               1        3
o11 : Matrix ZZ  <--- ZZ
i12 : w = matrix {{1}}

o12 = | 1 |

               1        1
o12 : Matrix ZZ  <--- ZZ
i13 : P = polyhedronFromHData(HS,v,hyperplanesTmp,w)

o13 = P

o13 : Polyhedron
i14 : vertices P

o14 = | -1 1 0  0 |
      | 0  0 -1 1 |
      | 1  1 1  1 |

               3        4
o14 : Matrix QQ  <--- QQ

See also Working with polyhedra.

Functions and methods returning a convex polyhedron :

Methods that use a convex polyhedron :

For the programmer

The object Polyhedron is a type, with ancestor classes PolyhedralObject < MutableHashTable < HashTable < Thing.