# Finding the “top” or “bottom” vertex of a simplex

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.

-

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