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

Working with polyhedra

We start with a polyhedron in 2-space which is the convexHull of a given set of points.
V = matrix {{0,2,-2,0},{-1,1,1,1}}
P = convexHull V

This gives an overview of the characteristics of the polyhedron. If we want to know more details, we can ask for them.

vertices P

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

(HS,v) = halfspaces P

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. To get the hyperplanes we use:

hyperplanes P

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.

rays P
linealitySpace P

Furthermore, we can construct the convex hull of a set of points and a set of rays.

R = matrix {{1},{0},{0}}
V1 = V || matrix {{1,1,1,1}}
P1 = convexHull(V1,R)
vertices P1

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

rays P1
hyperplanes P1

On the other hand we can construct a polyhedron as the intersection of affine half-spaces and affine hyperplanes.

HS = transpose (V || matrix {{-1,2,0,1}})
v = matrix {{1},{1},{1},{1}}
hyperplanesTmp = matrix {{1,1,1}}
w = matrix {{3}}
P2 = intersection(HS,v,hyperplanesTmp,w)

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

vertices P2

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

P3 = intersection(HS,v)
vertices P3
linealitySpace P3

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.

P4 = hypercube(3,2)
vertices P4

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

P5 = crossPolytope(3,3)
vertices P5

Furthermore the standard simplex (stdSimplex).

P6 = stdSimplex 2
vertices P6

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:

P7 = convexHull(P4,P5)
vertices P7

Or we can intersect them by using intersection:

P8 = intersection(P4,P5)
vertices P8

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:

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

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

Q = convexHull (-V)
P10 = P + Q
vertices P10

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

(C,L,M) = minkSummandCone P10
apply(values L, vertices)

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.

P11 = P * Q
vertices P11

The result is in QQ^4.

ambDim P11

To find out more about this polyhedron use for example.

fVector P11

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:

L = faces(1,P11)
vertP11 = vertices P11
apply(L, l -> vertP11_(l#0))

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

L = latticePoints P11
#L

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

C = tailCone P1
rays C

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:

P12 = polar P11
vertices P12