Normal fan

Remarks

Each $N_F$ is a polyhedral convex cone, and $\dim N_F = n - \dim F$. The collection $\mathcal{N}(P)$ is a complete fan:

1. every face of a cone of $\mathcal{N}(P)$ is a cone of $\mathcal{N}(P)$;
2. the intersection of two cones of $\mathcal{N}(P)$ is a face of each of them;
3. the union of all cones of $\mathcal{N}(P)$ is $\R^n$.

Inclusion is reversed: $F \subseteq G$ holds exactly when $N_G \subseteq N_F$. Each $N_F$ contains the orthogonal complement of the direction space of the affine hull of $P$. So the cones are pointed exactly when $P$ is full-dimensional, and then the vertices of $P$ give the $n$-dimensional cones and the facets give the rays.

Example: let $P = [-1,1]^2$. The vertex $(1,1)$ maximizes $\ip{u}{\cdot}$ exactly when $u_1 \ge 0$ and $u_2 \ge 0$, so its normal cone is the closed first quadrant. The edge $\set{1} \times [-1,1]$ is maximal exactly for $u_1 \ge 0$ and $u_2 = 0$, so its normal cone is the ray spanned by $(1,0)$. The face $P$ itself has normal cone $\set{0}$. So $\mathcal{N}(P)$ consists of the four closed quadrants, the four half-axes and the origin.

Non-example: the closed upper half-plane and the closed right half-plane do not form a fan, even with all their faces added. Their intersection is the first quadrant, which is not a face of either half-plane, so clause 2 fails.

Some authors use the functionals that are minimal on $F$ instead; this replaces each cone by its negative. The normal fan of a Minkowski sum $P + Q$ is the common refinement of the normal fans of $P$ and $Q$.