# intersection -- computes the intersection of half-spaces, hyperplanes, cones, and polyhedra

## Synopsis

• Usage:
P = intersection L
C = intersection M
C = intersection(M,N)
P = intersection(M,v)
P = intersection(M,v,N,w)
C = intersection(C1,C2)
P = intersection(P1,P2)
• Inputs:
• L, a list, containing any of the inputs below
• M, , with entries in ZZ or QQ
• N, , with entries in ZZ or QQ
• v, , with only one column and entries in ZZ or QQ
• w, , with only one column and entries in ZZ or QQ
• C1,
• C2,
• P1,
• P2,
• Outputs:

## Description

When inserting any of the combination of matrices into intersection, it considers the given matrices as defining inequalities and equalities. Thus, it either computes the polyhedron P = {p | M*p <= v and N*p = w }. Therefore, M and N must have the same number of columns, which will be the dimension of the ambient space, and M and v as well as N and w must have the same number of rows respectively. If N and w are omitted then the polyhedron is just given by the inequalities. If v and w are omitted then they are considered to be 0 so that the intersection is a cone and thus the output is of class Cone.

If two polyhedra or two cones are inserted, then the intersection of both arguments is computed if both arguments lie in the same ambient space. If both arguments are cones then the output is again a cone. Otherwise intersection returns a polyhedron.

If intersection is called for a list L, then the list may contain a combination of the following in any order.

• Inequalities, given by a sequence (M,v) of matrices over ZZ or QQ determining inequalities as above
• Equalities, given by a list {N,w} of matrices over ZZ or QQ determining equalities as above
• Cone
• Polyhedron

Then intersection computes the intersection 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.

The first use of intersection is to construct a cone:

 i1 : M = matrix {{1,2,3},{2,3,1},{3,1,2}} o1 = | 1 2 3 | | 2 3 1 | | 3 1 2 | 3 3 o1 : Matrix ZZ <--- ZZ i2 : C = intersection M o2 = {ambient dimension => 3 } dimension of lineality space => 0 dimension of the cone => 3 number of facets => 3 number of rays => 3 o2 : Cone

This is the cone of all points that are positive on the rows of the matrix M. If we add another row to this matrix and enter a condition vector we get a polyhedron:

 i3 : M = M || matrix {{-1,-1,-1}} o3 = | 1 2 3 | | 2 3 1 | | 3 1 2 | | -1 -1 -1 | 4 3 o3 : Matrix ZZ <--- ZZ i4 : v = matrix {{1},{2},{3},{4}} o4 = | 1 | | 2 | | 3 | | 4 | 4 1 o4 : Matrix ZZ <--- ZZ i5 : P = intersection(M,v) o5 = {ambient dimension => 3 } dimension of lineality space => 0 dimension of polyhedron => 3 number of facets => 4 number of rays => 0 number of vertices => 4 o5 : Polyhedron

This polyhedron, a tetrahedron, consists of all points p such that M*p <= v. If add a another pair of matrices, these conditions are evaluated as equalities. Thus we get a polyhedron which is not of full dimension. It is an intersection with an affine hyperplane.

 i6 : N = matrix {{1,2,0}} o6 = | 1 2 0 | 1 3 o6 : Matrix ZZ <--- ZZ i7 : w = matrix {{2}} o7 = | 2 | 1 1 o7 : Matrix ZZ <--- ZZ i8 : Q = intersection (M,v,N,w) o8 = {ambient dimension => 3 } dimension of lineality space => 0 dimension of polyhedron => 2 number of facets => 4 number of rays => 0 number of vertices => 4 o8 : Polyhedron

If we have another polyehdron or cone, we can also intersect them with the others.

 i9 : HC = intersection(matrix {{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}},matrix {{1},{1},{1},{1},{1},{1}}) o9 = {ambient dimension => 3 } dimension of lineality space => 0 dimension of polyhedron => 3 number of facets => 6 number of rays => 0 number of vertices => 8 o9 : Polyhedron i10 : C1 = intersection(C,HC) o10 = {ambient dimension => 3 } dimension of lineality space => 0 dimension of polyhedron => 3 number of facets => 6 number of rays => 0 number of vertices => 8 o10 : Polyhedron i11 : Q1 = intersection(P,HC) o11 = {ambient dimension => 3 } dimension of lineality space => 0 dimension of polyhedron => 3 number of facets => 9 number of rays => 0 number of vertices => 13 o11 : Polyhedron

## Ways to use intersection :

• "intersection(Cone,Cone)"
• "intersection(Cone,Polyhedron)"
• "intersection(List)"
• "intersection(Matrix)"
• "intersection(Matrix,Matrix)"
• "intersection(Matrix,Matrix,Matrix,Matrix)"
• "intersection(Polyhedron,Cone)"
• "intersection(Polyhedron,Polyhedron)"

## For the programmer

The object intersection is .