Can a point be closer to all the vertices of a convex polytope than another point inside that polytope?

Question

Consider a set $X = \{x_i \in \mathbb{R}^n\}$ and denote its convex hull $$ C \equiv \bigg\{ \sum_i \lambda_i x_i : \lambda_i \geq 0 \text{ for all } i \text{ and } \sum_i \lambda_i = 1 \bigg\}. $$

I would like to show that for any $c \in C$, there exists no $c' \in \mathbb{R}^n$ such that for all $x_i \in X$ $$ \|x_i-c'\|_\infty < \|x_i-c\|_\infty. $$ In other words, there is no point $c'$ that is simultaneously closer to all the points in $X$ than $c$. Alternatively, if you were to move $c$ closer to some $x_i$, you would automatically move away from another $x_{j}$. Distance is measured using the max-norm, but this probably also holds using other norms.

For instance, in case $X = \{x_1, x_2\}$, I can show for any $c \in C$ that the total distance to $x_1$ and $x_2$ is constant independently of the norm. Namely, \begin{align} \|x_1-c\| + \|x_2-c\| &= \| x_1 - (\lambda_1 x_1 + \lambda_2 x_2)\| + \|x_2 - (\lambda_1 x_1 + \lambda_2 x_2)\| \\ &= \|(1-\lambda_1) x_1 - \lambda_2 x_2\| + \|(1-\lambda_2) x_2 - \lambda_1 x_1\| \\ &= \|\lambda_2 ( x_1 - x_2 ) \| + \|\lambda_1 ( x_2 - x_1 ) \| \\ &= (\lambda_1 + \lambda_2) \|x_1 - x_2\| \\ &= \|x_1 - x_2\| \\ &= \text{constant}. \end{align} As a result, for any other $c' \in C$ \begin{align} \|x_1 - c'\| < \|x_1 - c\| \implies \|x_2 - c'\| > \|x_2 - c\| , \end{align} or \begin{align} \|x_2 - c'\| < \|x_2 - c\| \implies \|x_1 - c'\| > \|x_1 - c\| . \end{align} On the other hand, if $c' \notin C$, the triangle inequality quickly yields a similar result.

This idea does not solve my problem unfortunately as the total distance $\sum_i \|x_i-c\|$ is not constant when there are more than two points in $X$. For instance, consider in $\mathbb{R^2}$ the points $x_1 = (0,0)$, $x_2 = (1,0)$ and $x_3 = (0,1)$, and choose $c=x_1$ and $c'=x_2$.

Would anyone know a way to tackle this problem? It sounds so simple that there must already have been someone else who either proved it or found a counter-example.

Answer 1

It appears that this is false, here is a counterexample.

Let $x_1=(2,-1,-1)$, $x_2=(-1,2,-1)$ and $x_3=(-1,-1,2)$. The convex hull of these points contains the origin. The origin has $\infty$-distance 2 to all these points. However, the point $c'=(0.5,0.5,0.5)$, has $\infty$-distance 1.5 to all these points. Hence, for all $x_i\in X$, $$\|x_i-c'\|_\infty=1.5<2=\|x_i-0\|_\infty$$

Answer 2

Consider three points $P_1$, $P_2$, $P_3$, $P_i=(\delta_{ij})$ in $\mathbb{R}^3$ endowed with the standard $L_p$ norm.

If $1< p<\infty$ the norm is strictly convex. Therefore the minimization problem

$$\min \sum_{i=1}^3 \|PP_i\|_p$$

has a unique solution $P$. Due to the symmetry, the point $P$ lies on the line $x_1=x_2=x_3$.

Now, it turns out that for $p\ne 2$ the point of minimum is not $(1,1,1)$ ( it is not hard to find). By continuity, for $p= \infty$ a point of minimum is $(1/2,1/2,1/2)$. Hence this point is closer to $P_i$ than the point $(1/3,1/3,1/3)$.

Added: So it seems it works for all $p\ne 2$. For $p=2$ it's just the opposite, this requires another proof.

$\bf{Added:}$ Let's see why this is not true for the $l_p$ norm, $p \ne 2$, in dimension $n> 2$.

Consider $n$ points $P_i = (\delta_{ij})_{1\le j\le n}$, $1\le i \le n$.

The point $P$ with $\sum \|P-P_i\| $ smallest is unique, $P= (t, \ldots, t)$, with

$$t = \frac{1}{n^{\frac{1}{p-1}}+ 1}$$

For $p \ne 2$, this point $P$ is not in the convex hull of the $P_i$. Now consider the symmetric $P'_i$ of $P_i$ with respect to the $P$. We get a convex polytope $P_1 \ldots P_n P'_1 \ldots P'_n$ ( a prism) with center $P$. Moreover, for any other point $Q= (s, \ldots, s)$, and any $i$,

$$\delta = \|P-P_i\|< \|Q-P_j\|, \|Q-P'_k\|$$