Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How to find vertices a the polytope-intersection of two simplices, if I know the vertices of these simplices.

More precisely:

Let $T_1$ and $T_2$ be two regular $n-1$ dimensional simplices with vertices $(t,0,\ldots,0), (0,t,\ldots, 0),\ldots, (0, 0, \ldots, t)$ and $(t-n+1,1,\ldots, 1), (1, t-n+1, \ldots, 1), \ldots, (1,1, \ldots, t-n+1)$ resp.

The intersection of these simplices is a polytope $P$.

How to find vertices of it?

share|improve this question
    
FYI: The plural of "simplex" is "simplices" (just like "vertex" and "vertices"). –  Austin Mohr Aug 12 '12 at 18:50

1 Answer 1

up vote 1 down vote accepted

The first simplex is the intersection of the half-spaces $x_j \ge 0$ and the hyperplane $\sum_j x_j = t$. The second is the intersection of $x_j \le 1$ and $\sum_j x_j = t$. So $P$ is the intersection of the hypercube $0 \le x_j \le 1$ with the hyperplane $\sum_j x_j = t$. Note that any point in $P$ that has more than one non-integer coordinate can't be an extreme point of $P$. Let's suppose $m < t < m+1$ for some integer $m$, $0 < m < n$. Then the vertices of $P$ will be the $n {{n-1} \choose m}$ points that have $m$ coordinates $1$, $n-m-1$ coordinates $0$ and one $t - m$.

share|improve this answer
    
Thank you. But I am now confused, what would be the ages of these polytope--is it all possible distances between those points? –  user202312 Aug 15 '12 at 2:34
    
I assume you mean edges, not ages. Well, two vertices of $P$ should be joined by an edge if they share as many of the constraints $x_j = 0$ and $x_j = 1$, as possible. That is, vertices $X = (x_1,\ldots,x_n)$ and $Y=(y_1,\ldots,y_n)$ are neighbours if they are obtained by switching the coordinates where each has $t-m$: for some distinct $j$ and $k$ in $\{1,\ldots,n\}$, $x_j = y_k = t-m$, $x_k = y_j$, and $x_i = y_i$ otherwise. –  Robert Israel Aug 15 '12 at 5:01

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.