Covering of a polytope by balls with midpoints at the vertices

328 Views Asked by At

I have a polytope $P=\operatorname{conv}(v_1,\ldots,v_m)\subset \mathbb{R}^n$ and a ball $B_r(x)$ (with center $x\in \mathbb{R}^n$ and radius $r>0$), such that $P\subset B_r(x)$. Is the statement $$ P\subset \bigcup_{i=1}^mB_r(v_i)$$ true? Intuitively, I think it is true, but it is hard for me to prove it. For every point $w\in P$ I can show $d(w,v_i)\leq 2r$, since $d(w,v_i)\leq d(w,x)+d(x,v_i)\leq 2r$. But this only implies $$ P\subset B_{2r}(v_i)\quad\forall i\in\{1,\ldots,m\}.$$

Maybe it's better to formulate it without balls. I have $m$ points $v_1,\ldots, v_m$ and i know a point $x$ and a real number $r>0$ with $d(x,v_i)\leq r$ for all $v_i$. I claim for every $w\in\operatorname{conv}\{v_1,\ldots, v_m\}$ there is an $i$ with $d(w, v_i)\leq r$.

1

There are 1 best solutions below

3
On BEST ANSWER

Let $v\in conv(v_1\dots v_m)$, i.e., $v = \sum_i \lambda_i v_i$ with $\lambda_i\ge0$ and $\sum_i\lambda_i=1$. Using Euclidean distance, we get $$ \|v-v_i\|^2 = \|v-x+x-v_i\|^2 = \|v-x\|^2 + 2(v-x)^T(x-v_i) + \|x-v_i\|^2. $$ multiplying with $\lambda_i$ and summation with respect to $i$ gives $$\begin{split} \sum_i \lambda_i \|v-v_i\|^2 & = \|v-x\|^2 + \sum_i \lambda_i2(v-x)^T(x-v_i) + \sum_i\lambda_i\|x-v_i\|^2 \\ & = \|v-x\|^2 -2 \|v-x\|^2 + \sum_i\lambda_i\|x-v_i\|^2 \\ & = - \|v-x\|^2 + \sum_i\lambda_i\|x-v_i\|^2 , \end{split}$$ which is $$ \|v-x\|^2 + \sum_i \lambda_i \|v-v_i\|^2 = \sum_i\lambda_i\|x-v_i\|^2 . $$ Now the right-hand side is less than $r^2$ by assumption. This implies that at least one summand $\|v-v_i\|^2$ is less than $r^2$, which is the claim. (Note that it does not matter whether all balls are assumed to be open or all are assumed to be closed). I am curious how to prove such a result (or whether it is true at all) for other norms on $\mathbb R^n$.