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 polyhedron 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
|