A vertex $v$ of a simplex in $\mathbb{R}^n$ is a "top" vertex if there exists a point $p \neq v$ in the simplex with $v \ge p$ (i.e. $v\_1 \ge p\_1$, ... , $v\_n \ge p\_n$). Similarly, $v$ is a "bottom" vertex if there exists $p \neq v$ with $v \le p$.


It's not hard to show that any simplex has at least one top or bottom vertex. I'm looking for a test I can run (preferably in polynomial time) that identifies at least one such vertex, and whether it's top or bottom.


Thanks in advance for any advice!



Finding the "top" or "bottom" vertex of a simplex
Here is an outline of such a procedure.


Checking that a vertex $u$ is a top one can be done by solving a linear program, as follows:
write $p$ in baricentric coordinates, i.e. $p=p\_x=\sum\_{v\in V} x\_v v$, $x\_v\geq 0$ for any $v\in V$, and
$\sum\_{v\in V} x\_v=1$ (I denote by $V$ the set of vertices of the simplex).
To check $u$ is top is equivalent to checking that there exists $x=(x\_{v\_1},\dots,x\_{v\_{|V|}})$
satisfying $x\geq 0$, $\sum\_{v\in V} x\_v=1$, $u\geq p\_x$, and $x\_u<1$.


So you solve the linear program 
$$\min x\_u 
\text{ subject to $x\geq 0$, $\sum\_{v\in V} x\_v=1$, $u\geq p\_x$},$$ 
and it can be done in polynomial time. If the value of the objective is strictly less than 1 then $u$ is top.


Testing for $u$ to be bottom is essentially the same, just replace the inequalities $u\geq p\_x$ by $u\leq p\_x$.


Finally, do this for each vertex. Needless to say, if your simplex is given by inequalities rather than by vertices, it still can be done in polynomial time, as you can enumerate the vertices of a simplex in polynomial time.


