2 added 191 characters in body

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.

1

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.