# How to compute the projection of a polyhedron

Suppose that we have a polyhedron in $(x,y)$:

$P=\{ (x,y) \mid A_1 x +A_2 y \leq b \}$

How can I find the polyhedron $P_x=\{ x \mid (x,y)\in P \}$? In other words, I would like to write $P_x=\{x \mid A_x x \leq b_x\}$ for some $A_x$ and $b_x$.

There are several software packages around which will do the job for you.

Theoretically, you can solve the problem by Fourier-Motzkin eliminiation, see https://en.wikipedia.org/wiki/Fourier%E2%80%93Motzkin_elimination. The idea is to eliminate the existential quantifiers in $\mathbf{P}_\mathbf{x} = \{\mathbf{x}\mid\exists \mathbf{y}: A_1\mathbf{x} + A_2\mathbf{y}\leq \mathbf{b}\}$, where bold letters indicate vectors. Application of Fourier-Motzkin elimination yields the matrix $A_x$ and the vector $\mathbf{b}_x$. Be aware that the matrix and the vector will contain redundant rows in general.

This can be done with the PolyhedralSets package of Maple 2015. Here is an example in two dimensions.

with(PolyhedralSets):
p := PolyhedralSet([3 <= x, 10 <= y+x, x <= 10, y <= x+1]):
Plot(p);

px := Project(p, [x]):
Plot(px);

Display(px);

$$\dots,[y=0,9/2\leq x,x\leq 10],\dots$$

If your projection is $\rho$, then at least one vertex of $P$ is in the preimage (under $\rho$) of any vertex of $P_x$.

As the image of a compact set, we know $P_x$ is simply some interval $[x_0, x_1]$, and by the remark above you can find $x_0$ and $x_1$ as the smallest and largest $x$-coordinates of any vertex of $P$.

Things aren't as simple projecting into higher than $1$ dimension, but it's nice here.

• @ pjs36 : Are the vertices of $P$ given in the question under consideration? – user64494 Jun 29 '15 at 15:35
• @user64494 No, not unless you count "implicitly given". – pjs36 Jun 29 '15 at 17:23