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.

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),$$ respectively. Suppose also $m < t < m+1$ for some integer $m$, $0 < m < n$. The intersection of these simplices is a polytope $P$.

As was shown in this answer, the vertices of $P$ are the $n {{n-1} \choose m}$ points that have $m$ coordinates $1$, $n-m-1$ coordinates $0$ and one $t - m$.

How to show that the point of the polytope that maximizes the minimum distance to a vertex is a barycentre.

Thank you.

share|improve this question
3  
It is customary to try to ask questions in a form that do not look like you are giving us homework to do! :-) –  Mariano Suárez-Alvarez Aug 26 '12 at 17:26

1 Answer 1

up vote 0 down vote accepted

Yes, it is the barycentre $b = (t/n,\ldots,t/n)$. Let $F(x)$ be the minimum distance from $x$ to a vertex. Thus $F(b) = \sqrt{(n-m-1) (t/n)^2 + (t/n - t+m)^2 + m (1-t/n)^2}$.

Let $v$ be the vertex of $P$ where $v_i = 0$ for $1 \le i \le n-m-1$, $v_{n-m} = t-m$ and $v_i=1$ for $i\ge n-m+1$.

Suppose the maximum occurs at $c$. By symmetry, we may assume $c$ is sorted in ascending order, i.e. $c_1 \le c_2 \le \ldots \le c_n$. Then it is easy to see that the closest vertex to $c$ is $v$. Let $R = \{x \in P: x_1 \le x_2 \le ...x_n\}$. The function $F(x)$ is convex on $R$, so it takes its maximum at an extreme point of $R$. Now if $x \in R$ and $0 < x_i < x_{i+1} < 1$ for some $i \in \{1,\ldots,n-1\}$, then $x$ is not an extreme point because we could write $x = (y+z)/2$ where for some $\delta > 0$, $y_j = x_j + \delta (n-i)$ and $z_j = x_j - \delta (n-i)$ for $j \le i$ while $y_j = x_j - \delta i$ and $z_j = x_j + \delta i$ for $j > i$. So for an extreme point, we must have for all $i$, $x_i = 0$ or $x_i = x_{i+1}$ or $x_{i+1} = 1$. Thus the extreme points will be of the form $x_i = 0$ for $i \le i_0$, $x_i = s$ for $i_0 < i \le i_1$, $x_i = 1$ for $i > i_1$, where $(i_1 - i_0) s + (n - i_1) = t$. Note that $i_1 \ge n-m$ and $i_0 \le n-m-1$. It is possible that $i_0 = 0$ or $i_1 = n$. The case $i_0 = 0$, $i_1 = n$ is $b$, while the case $i_0 = n-m-1$, $i_1 = n-m$ is $v$. We have $$ \eqalign{F(x)^2 &= \sum_{i=i_0+1}^{n-m-1} s^2 + (t-m - s)^2 + \sum_{i=n-m+1}^{i_1} (1 - s)^2\cr &= (n-m-i_0-1) \left(\frac{t - n + i_1}{i_0 - i_0}\right)^2 + \left(t-m - \frac{t-n+i_1}{i_1-i_0}\right)^2 + (i_1 - n + m) \left(\frac{n-i_0 - t}{i_1 - i_0}\right)^2}$$ This seems like a mess, but let's consider it as a function $G(i_0, i_1)$ where $i_0$ and $i_1$ are continuous variables, $0 \le i_0 \le n-m-1$, $n-m \le i_1 \le n$. With Maple's help I get $$ \eqalign{\dfrac{\partial G}{\partial i_0} &= - \dfrac{(t-n+i_1)^2}{(i_1-i_0)^2} \le 0 \cr \dfrac{\partial G}{\partial i_1} &= \dfrac{(i_0 - n + t)^2}{(i_1-i_0)^2} \ge 0}$$ Thus the maximum must occur with $i_0 = 0, i_1 = n$, i.e. at $b$.

share|improve this answer
    
Thank you very much. Could you please split the formula for the sums in the answer. I can see only a half of it. Thank you. –  user202312 Aug 28 '12 at 2:01
    
$$ \eqalign{F(x)^2 &= \sum_{i=i_0+1}^{n-m-1} s^2 + (t-m - s)^2 + \sum_{i=n-m+1}^{i_1} (1 - s)^2\cr &= (n-m-i_0-1) \left(\frac{t - n + i_1}{i_0 - i_0}\right)^2 \cr &+ \left(t-m - \frac{t-n+i_1}{i_1-i_0}\right)^2 + (i_1 - n + m) \left(\frac{n-i_0 - t}{i_1 - i_0}\right)^2}$$ –  Robert Israel Aug 28 '12 at 17:20

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.