Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question
add comment

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer
    
This is very helpful - thank you. –  user21816 Mar 3 '12 at 20:17
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.