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