What is the equation of a facet and it's relation with all points of the polytope?

432 Views Asked by At

I was reading about polytopes and I came across about how to define equations of facets defining the polytope. The source I am reading from says

If $n$ is a normal vector to a facet $F$ of a polytope $P$ ( pointing outside the polytope ) then (1) all the points $p$ on the facet $F$ satisfy $n.p=f$ where $f$ is some constant. (2) Also for all the points $p$ lying on or inside the polytope $P$ the following holds $n.p<=f$.

How do I prove $(1)$ and $(2)$? I know that all the points on or inside the polytope will lie on or one side of the facet thus we might be getting the inequality $(2)$, but can't derive it. It would be really helpful if it could be explained with an example with a polytope in 2 or 3 dimension.

1

There are 1 best solutions below

1
On BEST ANSWER

The facet and the vectors

Let $n$ be the normal vector of the facet $F$ (which is is an affine hyperplane, both $n$ and $F$ magenta in the image) and $x_0$ be a position vector of the facet. Then every $x$ on the facet satisfies $$ 0 = n \cdot (x - x_0) = n \cdot x - n \cdot x_0 \iff \\ n \cdot x = n \cdot x_0 = f $$

For the second part:

  • If $n \cdot x = f = n \cdot x_0$ then $n \cdot x - n \cdot x_0 = 0$ and $n \cdot (x-x_0) = 0$ then $x - x_0$ and the endpoint of $x$ is within the plane (blue vectors).

  • If $n \cdot x = f_r < f = n \cdot x_0$ then $n \cdot x - n \cdot x_0 < 0$ and $n \cdot (x - x_0) < 0$ and thus $x - x_0$ and the endpoint of $x$ is below the facet (red vectors)

  • If $n \cdot x = f_g > f = n \cdot x_0$ then $n \cdot x - n \cdot x_0 > 0$ and $n \cdot (x - x_0) > 0$ and thus $x - x_0$ and the endpoint of $x$ is above the facet (green vectors).

The tiny vectors on the line $\alpha n$ are $(n \cdot (x-x_0)) n$, the vector part of $x-x_0$ pointing in $n$ direction, the green one positive, the red one negative.