Is it true that the set of points in $\mathbb R^n$ for which the sum of all distances from fixed $k$ points is $\le1$, is convex?
Asked
Active
Viewed 50 times
1 Answers
2
Yes, it is. Denote by $x_1,\ldots,x_k$ the fixed points and let $$F:= \left\{x \in \mathbb{R}^n; \sum_{i=1}^k |x_i-x| \leq 1 \right\}$$
Now let $x,y \in F$, $\lambda \in (0,1)$ arbritary and $x_{\lambda} := \lambda \cdot x + (1-\lambda) \cdot y$. Then $$\begin{align} \sum_{i=1}^k |x_i-x_{\lambda}| &= \sum_{i=1}^k \underbrace{|(\lambda \cdot x_i+(1-\lambda) \cdot x_i)-(\lambda \cdot x+(1-\lambda) \cdot y)|}_{|\lambda \cdot (x_i-x)+(1-\lambda) \cdot (x_i-y)|} \\ &\leq \lambda \cdot \underbrace{\sum_{i=1}^k |x_i-x|}_{\leq 1} + (1-\lambda) \cdot \underbrace{\sum_{i=1}^k |x_i-y|}_{\leq 1} \leq \lambda + (1-\lambda)=1 \end{align}$$
thus $x_{\lambda} \in F$ and this means that $F$ is convex.
saz
- 120,083