next | previous | forward | backward | up | index | toc

# convexHull -- computing the convex hull of points, rays and polyhedra

## Synopsis

• Usage:
P = convexHull M
P = convexHull(M,N)
P = convexHull(P1,P2)
P = convexHull L
• Inputs:
• M, , with entries inZZ or QQ
• N, , with entries inZZ or QQ
• P1,
• P2,
• L, a list
• Outputs:

## Description

convexHull computes the convex hull of the input. In the first two cases it considers the columns of M as a set of points and the columns of N (if given) as a set of rays and computes the polyhedron that is the convex hull of the points plus the rays. The two matrices must have the same number of rows, i.e. the columns must lie in the same ambient space. If N is not given or equal to 0, then the resulting polyhedron is compact and hence a polytope. The points need not be the vertices of the polyhedron. In the third case it computes the convex hull of P1 and P2 if they lie in the same ambient space. Finally, it computes the convex hull of a list L where the list may contain a combination of the following in any order.
• Vertices, given by a matrix M over ZZ or QQ
• Vertices and rays, given by a sequence (V,R)of two matrices over ZZ or QQ
• Cone
• Polyhedron

Then convexHull computes the convex hull of all inserted objects, if they are in the same ambient space, i.e. all matrices must have the same number of rows, which must equal the ambient dimension of all cones and polyhedra.

For example, consider the square in QQ^2:
 i1 : M = matrix {{1,1,-1,-1},{1,-1,1,-1}} o1 = | 1 1 -1 -1 | | 1 -1 1 -1 | 2 4 o1 : Matrix ZZ <--- ZZ i2 : P = convexHull M o2 = {ambient dimension => 2 } dimension of lineality space => 0 dimension of polyhedron => 2 number of facets => 4 number of rays => 0 number of vertices => 4 o2 : Polyhedron

If we add a ray, then it is not compact anymore:
 i3 : r = matrix {{1},{2}} o3 = | 1 | | 2 | 2 1 o3 : Matrix ZZ <--- ZZ i4 : P =convexHull(M,r) o4 = {ambient dimension => 2 } dimension of lineality space => 0 dimension of polyhedron => 2 number of facets => 4 number of rays => 1 number of vertices => 3 o4 : Polyhedron

If we add some more vertices to M then we get a hexagon:
 i5 : N = matrix {{-2,-2,0},{0,-2,-2}} o5 = | -2 -2 0 | | 0 -2 -2 | 2 3 o5 : Matrix ZZ <--- ZZ i6 : Q = convexHull(M|N) o6 = {ambient dimension => 2 } dimension of lineality space => 0 dimension of polyhedron => 2 number of facets => 6 number of rays => 0 number of vertices => 6 o6 : Polyhedron

Again if we add the ray r then the polyhedron is not compact:
 i7 : Q1 = convexHull(M|N,r) o7 = {ambient dimension => 2 } dimension of lineality space => 0 dimension of polyhedron => 2 number of facets => 5 number of rays => 1 number of vertices => 4 o7 : Polyhedron

To get this polyhedron we could also have used the application of convexHull to lists or pairs of polyhedra:
 i8 : P1 = convexHull {P,N} o8 = {ambient dimension => 2 } dimension of lineality space => 0 dimension of polyhedron => 2 number of facets => 5 number of rays => 1 number of vertices => 4 o8 : Polyhedron i9 : P1 == Q1 o9 = true i10 : P1 = convexHull(P,Q) o10 = {ambient dimension => 2 } dimension of lineality space => 0 dimension of polyhedron => 2 number of facets => 5 number of rays => 1 number of vertices => 4 o10 : Polyhedron i11 : P1 == Q1 o11 = true

## Ways to use convexHull :

• "convexHull(List)"
• "convexHull(Matrix)"
• "convexHull(Matrix,Matrix)"
• "convexHull(Polyhedron,Polyhedron)"

## For the programmer

The object convexHull is .