1
$\begingroup$

I am trying to understand how to prove the following, which seems to be a quite useful insight in terms of linear optimization. Unfortunately, I have a hard time with projective geometry. I'd greatly appreciate if someone could explain me how this can be done.

Suppose we have an $n$-dimensional polytope $P \subseteq \mathbb{R}^n$ and two distinct vertices $u$ and $v$. I want to show that there exists a projective transformation $P \rightarrow P'$ such that the transformed vertices $u'$ and $v'$ have the smallest, respectively the largest, $x_n$ coordinate among all vertices of $P'$.

Thanks in advance!

UPDATE: I think that this statement is not true if we replace "projective transformation" with "affine transformation". It might be true if we restrict to neighboring vertices $u$ and $v$ but I am not quite sure about that either. So if we suppose that this doesn't work in affine geometry, but it does in projective geometry, then I'd reckon that we somehow have to exploit the ability to map facets to the infinity hyperplane..

$\endgroup$
1
+50
$\begingroup$

I guess it is not very rigorous to say about projective transformations of subsets of an affine space, beacuse they should deal with points at infinity, which formally do not belong to the space. So I have the following hand-waving idea. Since the polytope $P$ is convex, there exist hyperplanes $H_u\ni u$ and $H_v\ni v$ supporting $P$. If they are parallel then we draw $x$-axis perpendicularly to them. Otherwise we move the intersection $H_u\cap H_v$ to infinity by a projective transformation, which will make the hyperplanes $H_u$ and $H_v$ parallel.

$\endgroup$
  • 1
    $\begingroup$ Thanks for the idea. I tried this using a particular polytope example and computed the projection etc, to get a better idea of projective transformation. What I still not have figured out. Lets say I use a projective transformation to move said intersection to infinity. What guarantees me that this projection is actually admissible for P, hence leaving me with a new proper polytope after transforming. $\endgroup$ – Doc Apr 12 at 19:13
  • $\begingroup$ @Doc Let $(x, n_u)=c_u$ and $(x, n_v)=c_v$ be the equations of the hyperplanes $H_u$ and $H_v$, respectively such that $(y,n_u)\le c_u$ and $(y,n_v)\le c_v$ for each $y\in P$. It is easy to check that a hyperplane $H$ determined by a equation $(x, n_u+n_v)=c_u+c_v$ contains $H_u\cap H_v$ and is disjoint from $P$. I guess when we make $H$ the infinity hyperplane, $P$ will be transformed to a proper polytope. $\endgroup$ – Alex Ravsky Apr 13 at 6:21

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.