2
$\begingroup$

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$.

$\endgroup$
2
$\begingroup$

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

Theoretically, you can solve the problem by Fourier-Motzkin 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.

$\endgroup$
2
$\begingroup$

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);

enter image description here

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

enter image description here

Display(px);

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

$\endgroup$
0
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.