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
|