Meaning cone, ray, fan for polytopes

Solution 1:

This answer is rather a story, not a pointed answer. The intuition will be supported by sage code and examples. Sage is free, installed by one click on linux boxes.

The definitions are already given, so there is nothing to do in this regard, i will only try to digest them, based on the example. And i will add a 2D-example.

Since $P(A,b)$ looks like a house, i'll call it so.

(1) First of all, we consider the polytope, (solid) polyhedral set from the OP given by $$ \underbrace{ \begin{bmatrix} 0 & 1 & 1 \\ 1 & 0 &1 \\ 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & -1 \\ 0 & 0& 1\\ 0 & -1& 0\\ 0 & -1& 1\\ -1 & 0& 0\\ -1 & 0& 1 \end{bmatrix}}_{=:A} \underbrace{ \begin{bmatrix} x\\ y\\ z \end{bmatrix}}_{=:v} \leq \underbrace{ \begin{bmatrix} 4\\ 4\\ 3\\ 3\\ 0\\ 2\\ 0\\ 1\\ 0\\ 1 \end{bmatrix}}_{=:b}\ . $$ This is explicitly the set of all $v=(x,y,z)\in\Bbb R^3$ satisfying all the following conditions: $$ \left\{ \begin{aligned} y+z & \le 4\ ,\\ x+z & \le 4\ ,\\ x & \le 3\ ,\\ y & \le 3\ ,\\ -z & \le 0\ ,\\ z & \le 2\ ,\\ -y & \le 0\ ,\\ -y+z & \le 1\ ,\\ -x & \le 0\ ,\\ -x+z & \le 1\ . \end{aligned} \right. $$ (It is convenient to swicht tacitly between $v=(x,y,z)$, simpler when writing humanly the inequations, and $x=(x_1,x_2,x_3)$, the sage preference.) Note that each equation is an equation determining a half-space, delimited by a (hyper)plane in the 3D-space. (In 2D, the space is a plane, a hyperplane is an affine set of codimension one, so it is a line, et caetera.) Each such half-space is a convex set, i.e. together with two points in it, the segment joining them is also in it.

The intersection of convex sets is a convex set. So we expect that the intersection of the half-planes determined by the above inequalities, i.e. the polytope $$ P(A,b):=\{\ v\in\Bbb R^d=\Bbb R^3\ :\ \underbrace{Av}_{\in\Bbb R^m=\Bbb R^{10}} \ge \underbrace{0 }_{\in\Bbb R^m=\Bbb R^{10}} \ \} $$ is also a convex set.

Among the above inequalities some are "very simple", for instance from $x\le 3$ and $-x\le 0$ we obtain $x\in[0,3]$. Similar restrictions appear for $y,z$, explicitly $y\in[0,3]$ and $z\in [0,2]$, so the whole "solid polyhedral set" $P(A,b)$, the whole house is at any rate contained in the "box" $[0,3]\times[0,3]\times[0,2]$. The ground of the house is the (solid) square $[0,3]\times[0,3]\times[0]$, and it is a $2$--dimensional (or $1=3-2$ codimensional) face. The roof has an upper platform, the intersection with the house with the (hyper)plane $z=2$, and it is the (solid) square $[1, 2]\times[1,2]\times[2]$. We have side walls, which are also faces of dimension $2$ (i.e. codimension $1$), for instance $[0,3]\times[0]\times[0,1]$. And on the roof there are also four dimension $2$ faces that let the water flow downwards.

Think about $d=3$ in the example as the dimension of the space containing the polyhedral set. And $m=10$ is the number of conditions (inequalities) used as plane delimiters for some half-spaces. The intersection of these half-spaces is our set of interest, it is a convex set, a (solid) polyhedral set. It may be that such a set is either bounded or unbounded. Our set in the example is bounded. So it is determined by its vertices (=extremal points). (In the sense that the convex hull of the set of these vertices is $P(A,b)$. In less mathematical terms, somehow intuitively...) One can put a mass (a real quantity $\ge 0$ in this physical world i accept today) in each such extremal point. Then this physical system has a mass center. All such possible mass centers are the given polyhedral set.

(1-2D) It may be good (at least for drawing) to also have a similar 2D-example. I will use the following set of inequalities, also allowing only $\le$ (so no $\ge$) while writing them: $$ \left\{ \begin{aligned} -x & \le 0\ ,\\ x & \le 3\ ,\qquad\text{ so }x\in[0,3]\\ -y & \le 0\ ,\\ y & \le 2\ ,\qquad\text{ so }y\in[0,2]\\ -x+y & \le 1\ ,\\ x+y & \le 4\ . \end{aligned} \right. $$ I hope that this is simpler to spot. From the first four inequalities we obtain $(x,y)\in[0,3]\times[0,2]$. And the other two conditions are "biting" from two corners. Is the whole system of inequalities "feasible", i.e. can we find some point satisfying all these conditions? Yes, $(0,0)$ is one such point. Some of the conditions are satisfied with the equality. But we can even do "better", the point $(1,1)$ satisfies them all with strict inequalities. So it is an "interior point", and we have indeed a $d=2$--dimensional "polyhedron", well a "solid polygon". The corresponding $A,b$ data can be extracted from: $$ \underbrace{ \begin{bmatrix} -1 & 0 \\ 1 & 0 \\ 0 & -1\\ 0 & 1\\ -1 & 1\\ 1 & 1 \end{bmatrix}}_{=:A} \underbrace{ \begin{bmatrix} x\\ y \end{bmatrix}}_{=:v} \leq \underbrace{ \begin{bmatrix} 0\\ 3\\ 0\\ 2\\ 1\\ 4 \end{bmatrix}}_{=:b}\ . $$

(2-2D) It may be a good idea to get computer support. For (1-2D) first. In sage, the above set can be declared as follows. The sage convention wants from us to rewrite the above, using $\ge$, and moving all terms on one side, so we pass from $Av\le b$ to $0\le b-Av$ and finally to $b-Av\ge 0$: $$ \underbrace{ \begin{bmatrix} 0 & 1 & 0 \\ 3 & -1 & 0 \\ 0 & 0 & 1\\ 2 & 0 & -1\\ 1 & 1 & -1\\ 4 & -1 & -1 \end{bmatrix}}_{=[b, -A} \begin{bmatrix} 1\\ x\\ y \end{bmatrix} \ge \begin{bmatrix} 0\\ 0\\ 0\\ 0\\ 0\\ 0 \end{bmatrix}\ . $$ Now we extract the coefficients and ask for...

b_A = matrix(QQ, 6, 3, [[0,  1,  0],
                        [3, -1,  0],
                        [0,  0,  1],
                        [2,  0, -1],
                        [1,  1, -1],
                        [4, -1, -1],])
P = Polyhedron(ieqs=b_A)

Now we can interactively ask for:

sage: P.inequalities()
(An inequality (-1, -1) x + 4 >= 0,
 An inequality (-1, 0) x + 3 >= 0,
 An inequality (0, -1) x + 2 >= 0,
 An inequality (1, 0) x + 0 >= 0,
 An inequality (0, 1) x + 0 >= 0,
 An inequality (1, -1) x + 1 >= 0)
sage: P.vertices()
(A vertex at (3, 0),
 A vertex at (2, 2),
 A vertex at (3, 1),
 A vertex at (1, 2),
 A vertex at (0, 1),
 A vertex at (0, 0))
sage: P.show()

Here, sage uses $x$ instead of $(x_1,x_2)$. Yes, the picture shown is

and we have the claimed vertices. And the show can go on with the polyhedral set in the OP:

We can ask for the faces in each dimension, and for the corresponding normal cones. But first we will introduce $h(P, u)$ in (4).

(2) The sage code and dialog for the set $P(A,b)$ from the OP is:

A = matrix( QQ, 10, 3,
        [[0, 1, 1], [1, 0, 1], [1, 0, 0], [0, 1, 0], [0, 0, -1],
        [0, 0, 1], [0,-1, 0], [0,-1, 1], [-1,0, 0], [-1,0,  1]])
        
b = matrix( QQ, 10, 1,
        [4, 4, 3, 3, 0, 2, 0, 1, 0, 1])

b_A = block_matrix([[b, -A]])
P = Polyhedron(ieqs=b_A)

This initializes P in sage. (And use it also below.) Then we can interactively ask for:

sage: P.inequalities()
(An inequality (-1, 0, -1) x + 4 >= 0,
 An inequality (-1, 0, 0) x + 3 >= 0,
 An inequality (0, -1, -1) x + 4 >= 0,
 An inequality (0, -1, 0) x + 3 >= 0,
 An inequality (0, 0, -1) x + 2 >= 0,
 An inequality (1, 0, 0) x + 0 >= 0,
 An inequality (0, 0, 1) x + 0 >= 0,
 An inequality (0, 1, -1) x + 1 >= 0,
 An inequality (0, 1, 0) x + 0 >= 0,
 An inequality (1, 0, -1) x + 1 >= 0)
sage: P.vertices()
(A vertex at (0, 3, 1),
 A vertex at (0, 0, 1),
 A vertex at (2, 2, 2),
 A vertex at (3, 3, 1),
 A vertex at (3, 3, 0),
 A vertex at (2, 1, 2),
 A vertex at (1, 1, 2),
 A vertex at (3, 0, 0),
 A vertex at (3, 0, 1),
 A vertex at (1, 2, 2),
 A vertex at (0, 0, 0),
 A vertex at (0, 3, 0))
sage: P.show()
Launched html viewer for Graphics3d Object

Then i get the image in the browser. It is a 3D-image, and we can rotate it.

(3) After these preliminaries, let us understand the set $$U(A)\ .$$

Using the above two examples. In the definition of the (solid) polyhedral set $P(A,b)$ we use $A$, $b$ as constants, they are previously fixed. And we have a non-trivial, non-empty set $P(A,b)$ in some cases, the input data $(A,b)$ is called feasible then, and $\emptyset$ else.

Now we fix $A$, and let $b$ run among all $b\in\Bbb R^m$. Think at the corresponding sets $P(A,b)$ as "deformations" of the given special situation of some $b_0$. I will try to illustrate this for the 2D-case.

Imagine we change the two $x$-conditions, and the two $y$-conditions, and the two remaining conditions "slightly". $$ \left\{ \begin{aligned} -x & \le 0\ ,\\ x & \le 3\ ,\qquad\text{ so }x\in[0,3]\\ -y & \le 0\ ,\\ y & \le 2\ ,\qquad\text{ so }y\in[0,2]\\ -x+y & \le 1\ ,\\ x+y & \le 4\ . \end{aligned} \right. \qquad\text{ into }\qquad \left\{ \begin{aligned} -x & \le -0.1\ ,\\ x & \le 3.2\ ,\qquad\text{ so }x\in[0.1\ ,\ 3.2]\\ -y & \le -0.3\ ,\\ y & \le 1.89\ ,\qquad\text{ so }y\in[0.3\ ,\ 1.89]\\ -x+y & \le 1.1\ ,\\ x+y & \le 4.1\ . \end{aligned} \right. $$ Then the corresponding picture is:

What happened? Every delimiting line was "slighlitly" moved parallely to itself corresponding to the deformations of the corresponding conditions. Some half-spaces are now "bigger" (w.r.t. the inclusion), other are "smaller". So chosing other $b$-values means moving the delimiting lines (in 2D, planes in 3D) in a parallel way, and then $P(A,d)$ is the new intersection of half-planes (in 2D, half-spaces in 3D) given by the new fronteers.

Now we are playing the following games starting with the original $P(A,b)$, $b=(0,3,0,2,1,4)\in\Bbb R^m=\Bbb R^6$, which implements the $m=6$ delimiting fronteers. We move the $\color{red}0$ from $b_0=(\color{red}{0},3,0,2,1,4)$ towards $3$, getting closer and closer to $3$. This moves the delimiting rectangular box $[\color{red}{0},3]\times[0,2]$ till it becomes smaller and smaller, of the shape $[\color{red}{3-\epsilon},3]\times[0,2]$, $\epsilon>0$. Yes, some conditions become superfluous now, but still, we have some thin (solid) trapezium left as $P(A,b)$. If we move this first component $b_1$ of $b=(b_1,b_2,b_3,b_4,b_5,b_6)\in\Bbb R^6$ beyond $3$, then there is nothing left, $P(A,b)=\emptyset$.

So far we have moved only one boundary condition. We can move two of them, but let us move all of them, we try to get closer to the situation where the set $P(A,b)$ becomes smaller and smaller, becomes a point (or something living in less dimensions) and "vanishes". A way of thinking of a six-dimensional move that does this is as follows. Let us focus on some fixed point say $(1,1)$. Now we move all boundaries as we would move the lens of a camera (parallely),

lens camera movement

so that we have one point when all boundaries touch $w'=(1,2)$, say. Which is the value for this $b$-parameter. Well we plug in this value $w'=(x,y)=(1,2)$ into the function $v\to Av$, and get $w'\to Aw'=b'=(-1,1,-2,2,1,3)$.

Note that when we plug in the $b$-value as it was in the 2D-example, $b=(0,3,0,2,1,4)$, we can always slightly change each component, still having a feasible $P(A,b)$. But for the above $b'$ we have to be careful. There is a strict movement in each component, either in direction "bigger" or in direction "smaller", but not both. We can do the same with $w''=(1,1)$ and $w^\dagger=(0,1)$, getting $b''=Aw''=(-1,1,-1,1,0,2)$ and $b^\dagger=Aw^\dagger=(0,0,-1,1,1,1)$.

And observe that parallely to the fact that $w', w'', w^\dagger$ are on a line, also the points $b',b'',b^\dagger$ are on a line. And moreover, $w''$ being on the segment $[w',w^\dagger]$ (mid point even) in $\Bbb R^2$, makes $b''$ sit on the segment $[b',b^\dagger]$ (also as the mid point) by linearity via $A$.

Now we can say some words on $U(A)$.

It contains all "boundary parameters" $b$, so that the corresponding system of inequalities has at least a solution. In the case of the matrix $A$ from the OP, imagine all possibilities to move the (hyper)planes delimiting the house $P(A,b)$ to get in the same $\Bbb R^3$ a house (in the sky or underground) with the same kind of walls, i.e. move them parallely up and down, to the left to the right, in the depth, et caetera. All possible such movements are parametrized by some $b'$, and if there is a small place for an ant in the house, well for a point at least, then $b'\in U(A)$. We have seen above some possibilities for such a $b'$. In some case, the new house has only a thin shape to live in near the wall $x=3$. In some other cases, we have collapsed the house to one point with all planes delimiting it, the house can only give place for the point $w'$, resp. $w''$, resp. $w^\dagger$, etc. but to make the house become a point it is of course enough to move less planes to touch that one point.

We have thus a big freedom to move the roof platform $[1,2]^2\times [2]$ upwards, the ground "face" $[0,3]^2\times[0]$ downwards, the left wall to the left, etc. from the starting (or some other feasible) $b$, this means moving from $b$ to an other configuration obtained by going correspondingly in one direction with either $b_1$, $b_2$, ... , but when we move in the other direction, there is a point of collapsing the house to something in a plane, where no thin $3$-dimensional ant can live in. And then, the house vanishes. (Becomes the empty set.) This was the story of $U(A)$.

(4) What is the support function $u\to h(P,u)$ for some polytope $P$? We will illustrate this for $P=P(A,b)$ from the OP. By definition, for a general $P$, it is $$ h(P, u):=\max_{x\in P}x\cdot u\ . $$ Here, $x\cdot u$ is the scalar product of the vectors $x$ and $u$. For instance, if $u=(0,0,1)$, the vector pointing to the sky in the lanscape of our house $P=P(A,b)$, then for some $x=(x_1,x_2,x_3)\in P(A,b)$ the scalar product is $x_3$, its maximal value is $2$, taken for the points of the roof platform. So having it, and knowing only the house, not the inequalities defining it, we can already write an inequality, $(0,0,1)\cdot(x_1,x_2,x_3)\le 2$. This means $h(P,(0,0,1))=2$. So (up to norming issues), we get the corresponding $b$-component from the equation for the line in $A$ which is proportional to this $u$. Similarly, we may take $u=(0,0,-1)$, then the scalar product is $-x_1$, and the maximum is zero. (On the ground.) We write this as $h(P, (0,0,-1))=0$. But there are also some other directions, not the ones perpendicular / normal to the one or other face (e.g. wall, roof, ground, in dimension two, or vertical line where two walls intersect, in dimension one, or even one corner, dimension zero) of the house. For instance what happens with $u=(2,3,4)$. Well, we draw the vector as an arrow in the space, and imagine a plane perpendicular / normal to this arrow, and we push it so far in the direction of the arrow till we have the last point of contact with the house. In this point we get the maximal value for $h(P, (2,3,4))$. (It is somewhere on the roof. We have to intersect with each plane determined by the faces of the roof.)

(5) What is the normal cone of a face? To be specific, let us consider the face $F=[1,2]^2\times[2]$, the roof platform. A point on this face is of the shape $(x_1, x_2,3)$ with $1\le x_1,x_2\le 2$.

By definition, for this face, $$ \mathcal N(F,P) =\{ \ v=(v_1,v_2,v_3)\in\Bbb R^3\ :\ h(P, v):=\max_{y\in P}y\cdot v \text{ in taken in one and each }x\in F \ \} \ . $$ (It is clear that if some $v$ is in this normal cone, than any positive scalar times $v$ is also in there.) In other words, some $v$ is in the normal cone $\mathcal N(F,P)$ of this face if and only if, taking a plane perpendicular / normal on $v$ and pushing it so far as possible in the direction of the arrow $v$ we touch the house for "the last time" in one and each point in the face $F$. So $v$ is normal to the plane the face $F$ sits in, and we have to go in its direction (not in the opposite direction). The immediate guess is that the normal cone contains only the vector $(0,0,1)$, normal to $F$ and making $F$ the "last face touched in this direction", and those obtained from it by multiplication with a scalar $\ge 0$. The normal cone is thus a ray, a half-line, starting in $0=(0,0,0)$ and pointing in the direction $(0,0,1)$.

The same can be done with all other $2$-dimensional faces. To have the confirmation, and the computation for all $2$--faces, the following code is my typist:

Since we can do it, we ask sage for this normal cone. I am using sage as a typist, there is no need to understand the code. (But it may be useful if one wants to adapt it to an other situation.)

for F in P.faces(2):
    # F is a 2-dimensional face of P
    print('Face with vertices {}'.format([tuple(v) for v in F.vertices()]))
    NC = F.normal_cone()    # just ask for it, we know it is a ray starting from the origin
    print(f'Its normal cone has {NC.vertices()} and {NC.rays()}\n')

We let this run and get:

Face with vertices [(0, 3, 1), (0, 0, 1), (1, 1, 2), (1, 2, 2)]
Its normal cone has (A vertex at (0, 0, 0),) and (A ray in the direction (-1, 0, 1),)

Face with vertices [(0, 0, 1), (3, 0, 0), (3, 0, 1), (0, 0, 0)]
Its normal cone has (A vertex at (0, 0, 0),) and (A ray in the direction (0, -1, 0),)

Face with vertices [(0, 0, 1), (2, 1, 2), (1, 1, 2), (3, 0, 1)]
Its normal cone has (A vertex at (0, 0, 0),) and (A ray in the direction (0, -1, 1),)

Face with vertices [(3, 3, 0), (3, 0, 0), (0, 0, 0), (0, 3, 0)]
Its normal cone has (A vertex at (0, 0, 0),) and (A ray in the direction (0, 0, -1),)

Face with vertices [(0, 3, 1), (0, 0, 1), (0, 0, 0), (0, 3, 0)]
Its normal cone has (A vertex at (0, 0, 0),) and (A ray in the direction (-1, 0, 0),)

Face with vertices [(2, 2, 2), (2, 1, 2), (1, 1, 2), (1, 2, 2)]
Its normal cone has (A vertex at (0, 0, 0),) and (A ray in the direction (0, 0, 1),)

Face with vertices [(0, 3, 1), (3, 3, 1), (3, 3, 0), (0, 3, 0)]
Its normal cone has (A vertex at (0, 0, 0),) and (A ray in the direction (0, 1, 0),)

Face with vertices [(0, 3, 1), (2, 2, 2), (3, 3, 1), (1, 2, 2)]
Its normal cone has (A vertex at (0, 0, 0),) and (A ray in the direction (0, 1, 1),)

Face with vertices [(3, 3, 1), (3, 3, 0), (3, 0, 0), (3, 0, 1)]
Its normal cone has (A vertex at (0, 0, 0),) and (A ray in the direction (1, 0, 0),)

Face with vertices [(2, 2, 2), (3, 3, 1), (2, 1, 2), (3, 0, 1)]
Its normal cone has (A vertex at (0, 0, 0),) and (A ray in the direction (1, 0, 1),)

Let us consider now a $1$-dimensional face. To make things complicated, i will take an edge of the roof platform, $F=[1,2]\times[2]\times[2]$. Is is determined by two vertices, $(1,2,2)$ and $(2,2,2)$. Now imagine again a vector $v$, together with its normal plane, and we push as far as possible this plane in the $v$ direction, till it touches for the last time the house. When is this the case for the entire face $F$? It is clear that the last touch is this whole face $F$, so the "last plane" contains the face $F$, and thus also the line supporting it. Now we look at all planes "rotating" around this line parametrized by $(t,2,2)=(0,2,2)+t(1,0,0)$ or given by the equations $x_2=x_3=2$. Among all these planes two of them are "interesting", the plane of the roof platform $R$, which contains the $2$--face $[1,2]^2\times [2]$ and the oblique roof wall $W$ behind, of trapezoidal shape with parallel bases/edges $F=[1,2]\times[2]\times[2]$ and $F'=[0,3]\times[3]\times[1]$. We start with this plane $W$ and rotate it around the face $F$ till it becomes $R$, such that the house remains touched only in $F$. It is clear that for each plane in this family the face $F$ is the "last touch". But we are not interested in these planes, but rather in the vectors $v$ perpendicular to the planes. Which are these vectors. First of all, they are perpendicular to (the direction of) $F$ (and of the line supporting it), so to $(1,0,0)$ (see the $t$-parametrization). So for such a $v$, from $v\cdot(1,0,0)=0$ we get $v_1=0$. Then in the other two remained coordinates, $v_2,v_3$, we move from the perpendicular to the roof $R$ to the perpendicular to the roof wall $W$. This set is indeed a cone, and we can draw it.

Well, when we draw, we have to draw a cone based in $(0,0)$, but in our thoughts, the $1$-dimensional face $F$ and the $2$-dimensional faces containing it were geometrically the essence of the construction. So by convention, and by easy identification of the normal cones, when we draw more of them, it is usual to draw a translated version of them, namely the version moved to the face.

Here is the code and the shape of the normal cones for the $1$-faces, i assume that P is as above.

P = Polyhedron(ieqs=b_A)
for F in P.faces(1):
    # F is a 2-dimensional face of P
    print('Face with vertices {}'.format([tuple(v) for v in F.vertices()]))
    NC = F.normal_cone()    # just ask for it, we know it is a ray starting from the origin
    print(f'Its normal cone has\n- {NC.vertices()} and\n- {NC.rays()}\n')

It gives:

Face with vertices [(0, 0, 1), (1, 1, 2)]
Its normal cone has
- (A vertex at (0, 0, 0),) and
- (A ray in the direction (-1, 0, 1), A ray in the direction (0, -1, 1))

Face with vertices [(0, 3, 1), (0, 0, 1)]
Its normal cone has
- (A vertex at (0, 0, 0),) and
- (A ray in the direction (-1, 0, 0), A ray in the direction (-1, 0, 1))

Face with vertices [(1, 1, 2), (1, 2, 2)]
Its normal cone has
- (A vertex at (0, 0, 0),) and
- (A ray in the direction (-1, 0, 1), A ray in the direction (0, 0, 1))

Face with vertices [(0, 3, 1), (1, 2, 2)]
Its normal cone has
- (A vertex at (0, 0, 0),) and
- (A ray in the direction (-1, 0, 1), A ray in the direction (0, 1, 1))

Face with vertices [(0, 0, 1), (3, 0, 1)]
Its normal cone has
- (A vertex at (0, 0, 0),) and
- (A ray in the direction (0, -1, 0), A ray in the direction (0, -1, 1))

Face with vertices [(3, 0, 0), (0, 0, 0)]
Its normal cone has
- (A vertex at (0, 0, 0),) and
- (A ray in the direction (0, -1, 0), A ray in the direction (0, 0, -1))

Face with vertices [(0, 0, 1), (0, 0, 0)]
Its normal cone has
- (A vertex at (0, 0, 0),) and
- (A ray in the direction (-1, 0, 0), A ray in the direction (0, -1, 0))

Face with vertices [(3, 0, 0), (3, 0, 1)]
Its normal cone has
- (A vertex at (0, 0, 0),) and
- (A ray in the direction (0, -1, 0), A ray in the direction (1, 0, 0))

Face with vertices [(2, 1, 2), (1, 1, 2)]
Its normal cone has
- (A vertex at (0, 0, 0),) and
- (A ray in the direction (0, -1, 1), A ray in the direction (0, 0, 1))

Face with vertices [(2, 1, 2), (3, 0, 1)]
Its normal cone has
- (A vertex at (0, 0, 0),) and
- (A ray in the direction (0, -1, 1), A ray in the direction (1, 0, 1))

Face with vertices [(0, 0, 0), (0, 3, 0)]
Its normal cone has
- (A vertex at (0, 0, 0),) and
- (A ray in the direction (-1, 0, 0), A ray in the direction (0, 0, -1))

Face with vertices [(3, 3, 0), (0, 3, 0)]
Its normal cone has
- (A vertex at (0, 0, 0),) and
- (A ray in the direction (0, 0, -1), A ray in the direction (0, 1, 0))

Face with vertices [(3, 3, 0), (3, 0, 0)]
Its normal cone has
- (A vertex at (0, 0, 0),) and
- (A ray in the direction (0, 0, -1), A ray in the direction (1, 0, 0))

Face with vertices [(0, 3, 1), (0, 3, 0)]
Its normal cone has
- (A vertex at (0, 0, 0),) and
- (A ray in the direction (-1, 0, 0), A ray in the direction (0, 1, 0))

Face with vertices [(2, 2, 2), (1, 2, 2)]
Its normal cone has
- (A vertex at (0, 0, 0),) and
- (A ray in the direction (0, 0, 1), A ray in the direction (0, 1, 1))

Face with vertices [(2, 2, 2), (2, 1, 2)]
Its normal cone has
- (A vertex at (0, 0, 0),) and
- (A ray in the direction (0, 0, 1), A ray in the direction (1, 0, 1))

Face with vertices [(0, 3, 1), (3, 3, 1)]
Its normal cone has
- (A vertex at (0, 0, 0),) and
- (A ray in the direction (0, 1, 0), A ray in the direction (0, 1, 1))

Face with vertices [(3, 3, 1), (3, 3, 0)]
Its normal cone has
- (A vertex at (0, 0, 0),) and
- (A ray in the direction (0, 1, 0), A ray in the direction (1, 0, 0))

Face with vertices [(2, 2, 2), (3, 3, 1)]
Its normal cone has
- (A vertex at (0, 0, 0),) and
- (A ray in the direction (0, 1, 1), A ray in the direction (1, 0, 1))

Face with vertices [(3, 3, 1), (3, 0, 1)]
Its normal cone has
- (A vertex at (0, 0, 0),) and
- (A ray in the direction (1, 0, 0), A ray in the direction (1, 0, 1))

Similarly, when we consider a vertex, a $0$-dimensional face, then its cone starts in zero and is delimited by three rays, those normals of the $2$--faces determining it. For instance:

sage: P = Polyhedron(ieqs=b_A)
....: for F in P.faces(0):
....:     # F is a 2-dimensional face of P
....:     print('Face with vertices {}'.format([tuple(v) for v in F.vertices()]))
....:     NC = F.normal_cone()    # just ask for it, we know it is a ray starting from the origin
....:     print(f'Its normal cone has\n- {NC.vertices()} and\n- {NC.rays()}\n')
....:     break
....: 
Face with vertices [(0, 0, 1)]
Its normal cone has
- (A vertex at (0, 0, 0),) and
- (A ray in the direction (-1, 0, 0),
   A ray in the direction (-1, 0, 1),
   A ray in the direction (0, -1, 0), 
   A ray in the direction (0, -1, 1))

(The result was manually rearranged.)

(6) Complete fan. We collect all the cones above. (In my convention, the origin is part of these cones. But tomorrow it may be different. One should read the definitions to see if this is the case, also if the cones in the fan are containing the boundary or not.)

Note that in each direction $v$ we go, there is a last touch of the house when moving a $v$-normal plane (from far away, $-\infty$ in its direction, in the direction of $+\infty$ on it line $\Bbb R v$), this last touch is a vertex, or an edge, or a $2$-face, at any rate, it comes somewhere in the one or the other cone.

So the union of all these fans is $\Bbb R^3$, the entire space. (Without zero, depending on convention.) This means that the fan is complete.

(7) Combinatorially equivalent polytopes. We start with our house, $P(A,b)$. And move the "walls" ($2$-faces) parallely. (The roof platform, and the other oblique roof parts are now walls.) This is parametrically done by using some $b'$ instead of $b$.

If the "shape" of the house remains, i.e. we have in the new house $P(A,b')$ the same number of faces, thus in correspondence $W\to W'$, wall $W$ of the house $P(A,b)$ is bijectively associated to wall $W'$ of $P(A,b')$, it is clear that the normal cone for $W$ is the same as for $W'$. And the same for some $1$--face, i.e. edge $F=W_1\cap W_2$, the normal cone is the same as the one for $F':=W_1'\cap W_2'$ in the new house.

(So please do not move the left wall to the right so far, that it eliminated the roof platform from the house.)

So the normal fans of the old and the new house coincide. This can be safely taken as definition for the combinatorial equivalence.

(8) How to see the decomposition of the house as "sum" of some pieces?

Let us take the (solid) "roof" $R$ only, it is in the picture Figure 1 from the link the (solid) pyramid, that roof placed on the ground.

Consider also the cube $C=[0,1]^3$. What is $R+C$?

It is the set obtained as the union of all $R+c$ for $c$ in the cube $C$. So we take $R$ and move it in all $x,y,z$ directions, at most one unit. Some points will be taken more than once in this movement. But note that the upper vertex of the pyramid can reach at most the height $2$, and in this case it can realize exactly the points on the roof platform.

This illustrates that our house is decomposed as a sum in the shape $R+C$.

Now $C$ further decomposes as the sum of elements on the three segments $[0,1]\times[0]\times[0]$, it corresponds to the red segment in Figre one, but i want the opposite orientation, $[0]\times[0,1]\times[0]$, the green segment with opposite orientation, and $[0]\times[0]\times[0, 1]$, the blue segment.

(I have to submit... almost too long to be shown, there is a limit of characters, i often hit it. For the rest, how to get the $b$-inequalities, a new post is needed. If there is a real interest, the post will be here as soon as my typing skills allow it.)

Solution 2:

The article investigates the set $U(A) = \{b : \exists x\; Ax \leq b \}$. In words, that is the set of vectors $b$ for which $Ax \leq b$ has a solution, that is, for which the set $\{x : Ax \leq b\}$ is not empty. Via Farkas Lemma, they express the set as $U(A) = \{ b : y^Tb \geq 0 \; \forall y \in S\}$ with $S = \{ y \geq 0 : A^Ty=0 \}$.

Without going into how the set $S$ is derived, we can already make a few remarks. Since $A \in \mathbb{R}^{10 \times 3}$ in the example, $S \subset \mathbb{R}_+^{10}$. Moreover, if $y \in S$, then also $\alpha y \in S$ for any $\alpha \geq 0$. Therefore, $S$ is a cone. The set $S$ is also convex, so it is a convex cone. The set $\{ \alpha y : \alpha \geq 0 \}$ is called a ray, which is just a half-line with one endpoint at the origin. A ray of $S$ that cannot be expressed as a convex combination of other rays of $S$ is called an extreme ray of $S$. Figure 1 of this article has an illustration of the extreme rays of a cone. If $-y\in S$ for some $y\in S$, $S$ is said to contain a line. A cone that does not contain any lines is a pointed cone. A cone is defined (or generated) by the set of its (possibly infinite number of) lines and rays.

To verify if a given vector $b$ is an element of $U(A) = \{ b : y^Tb \geq 0 \; \forall y \in S\}$ one does not need to check all elements in $S$, but it suffices to check whether $y^Tb \geq 0$ for one nonzero element of each extreme ray of $S$ and $y^Tb=0$ for one nonzero element of each extreme line of $S$ (it then automatically holds for all elements in $S$). The remainder of the article is about deriving the extreme rays of $S$. As a spoiler they already provide the final result (those 9 inequalities involving $b_i$), but you cannot understand why they are correct without reading the rest of the paper. At this point you can however check that indeed $A^Ty=0$ for each vector $y$.

The set $S$ is a polytope, since it is the finite intersection of closed halfspaces. The face of a polytope is visually one of the sides, edges or corners of the polytope. The mathematical definition of a face is $F = S \cap\{y:c^Ty=d\}$ where $c$ and $d$ are such that $c^Ty \leq d$ for all $y \in S$ ($c^Ty \leq d$ is a valid inequality). Each face $F$ has an associated normal cone, $N(F,S) = \{ v : v^Ty \geq v^Tz \; \forall y \in F \; \forall z \in S\}$. The normal cone (which is a convex cone) is the set of all vectors that are orthogonal to the face. An illustration can be found in this question (left panel). The set of all normal cones is called the normal fan. An illutration is found here, and indeed it covers every angle which means it is a complete fan.