Lipschitz functions in $\mathbb{R}^n, \ \ \mathbb{R}^m$, extension

Question

I've found the following lemma :

Let $\{x_1, . . . , x_k\}$ be a finite collection of points in $\mathbb{R}^n$ , and let $\{y_1, . . . , y_k\}$ be a collection of points in $\mathbb{R}^m$, such that

$$|x_i - x_j|\le |y_i - y_j| \ \ \ \ \ \ \forall i,j \in \{1,...,k\}$$.

If $r_1, . . . , r_k$ are positive numbers such that

$$\bigcap _{i=1} ^{k} \overline{B}(x_i, r_i) \neq \emptyset,$$ then $$\bigcap _{i=1} ^{k} \overline{B}(y_i, r_i) \neq \emptyset$$.

My question is: how does this lemma imply that

if we let $F = \{x_1, . . . , x_k\} \subset \mathbb{R}^n$ , $ f : F \rightarrow \mathbb{R}^m$ be a $1$-Lipschitz map, let $x \in \mathbb{R}^n$, set $r_i:= |x − x_i|$ and $y_i:= f(x_i)$,

then by this lemma there exists a point $y \in \mathbb{R}^m$ such that $|y − f(x_i)| \le |x − x_i|$ for each $i$.

It may be that it's a stupid question and this result is really obvious, but I would appreciate an answer anyway.

Thank you.

Answer 1

First of all, your first inequality is reversed and should read $$ |y_i - y_j| \leq |x_i - x_j| \hspace{0.5in} \forall i,j. $$

Now let's just work through everything. It's easier than it looks.

First of all, if $f$ is $1$-Lipschitz and $y_i = f(x_i)$, then the above (corrected) inequality is satisfied. ($1$-Lipschitz maps shrink all distances.)

With your choice of $r_i=|x-x_i|$, we have that each closed ball $\overline{B}(x_i,r_i)$ contains the point $x$, and thus $$ \bigcap \overline{B}(x_i,r_i) \neq \emptyset $$

By the lemma, we therefore have $$\bigcap \overline{B}(f(x_i),r_i) \neq \emptyset.$$

So there is some $y$ which is in $\overline{B}(f(x_i),r_i)$ for all $i$. In other words, $$ |y-f(x_i)| \leq r_i = |x-x_i| \hspace{0.5in} \forall i, $$ which is exactly what you wanted.

(For anyone else interested, this is the key step in a proof of Kirszbraun's Theorem, and it can be found in Heinonen's "Lectures on Lipschitz analysis" online here.)

Answer 2

My geometric intuition says following. Let $C$ be the convex hull of the set $F$. It is easy to check that there is a unique point $x’\in C$ such that $|x’-x|=|C-x|=(def) \min\{|c-x|:c\in C\}$. Then $|x’-x_i|\le |x-x_i|$ for each $i$. There exist non-negative numbers $\lambda_i$, $1\le i\le k$ with $\sum\lambda_i=1$ such that $x’=\sum\lambda_i x_i$. Put $y=\sum\lambda_i y_i$.