0
$\begingroup$

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?

  • 0
    FYI: The plural of "simplex" is "simplices" (just like "vertex" and "vertices").2012-08-12

1 Answers 1

2

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

  • 0
    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.2012-08-15