Showing: point of polytope which maximizes the minimum distance to a vertex is a barycentre?

Question

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.

Answer 1

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