$\displaystyle\tilde{\ell}_{i}=\\{u\in{\bf R}^{2}:\langle{{\bf
h}_{i},u}\rangle=\delta\,\|{\bf h}_{i}\|_{1}\\},~{}~{}~{}i=1,2.$ (4.30)

Let

$\displaystyle A=\left(\begin{array}[]{ll}\cos\varphi_{1}&\sin\varphi_{1}\\\
\cos\varphi_{2}&\sin\varphi_{2}\end{array}\right)~{}~{}~{}\text{and
let}~{}~{}~{}\Delta=\det A=\sin(\varphi_{2}-\varphi_{1}).$ (4.33)

See (4.27). (Clearly, $\Delta\neq 0$ because ${\bf h}_{1}\nparallel{\bf
h}_{2}$.) We know that

$X_{1}=(s_{1},s_{2})=\ell_{1}\cap\tilde{\ell}_{2}$

so that, thanks to (4.26) and (4.30), the vector $(s_{1},s_{2})$ is the
solution of the system of linear equations

$A\left(\begin{array}[]{l}s_{1}\\\
s_{2}\end{array}\right)=\left(\begin{array}[]{l}\hskip 14.22636pt0\\\
\delta\,\|{\bf h}_{2}\|_{1}\end{array}\right).$

Therefore,

$\displaystyle
s_{1}=\frac{1}{\Delta}\,\left|\begin{array}[]{ll}0&\sin\varphi_{1}\\\
\delta\,\|{\bf
h}_{2}\|_{1}&\sin\varphi_{2}\end{array}\right|=-\frac{\delta}{\Delta}\,\|{\bf
h}_{2}\|_{1}\,\sin\varphi_{1}~{}~{}~{}\text{and}~{}~{}~{}s_{2}=\frac{\delta}{\Delta}\,\|{\bf
h}_{2}\|_{1}\,\cos\varphi_{1}.$ (4.36)

Thus,

$\displaystyle X_{1}=\frac{\delta}{\Delta}\,\|{\bf
h}_{2}\|_{1}\,(-\sin\varphi_{1},\cos\varphi_{1}).$ (4.37)

In the same way we prove that

$\displaystyle X_{2}=\frac{\delta}{\Delta}\,\|{\bf
h}_{1}\|_{1}\,(\sin\varphi_{2},-\cos\varphi_{2}).$ (4.38)

###### Lemma 4.10

Inequality (4.15) holds provided $\varphi_{1}\in(\pi/2,\pi)$ and
$\varphi_{2}\in(\varphi_{1},\pi)$.

Proof. We recall that in the case under consideration

${\bf h}_{i}=(\cos\varphi_{i},\sin\varphi_{i})\in{\bf
S}_{1}~{}~{}~{}\text{where}~{}~{}~{}\varphi_{i}\in(\pi/2,\pi),~{}~{}~{}i=1,2.$

Hence,
$(\operatorname{sign}(\cos\varphi_{i}),\operatorname{sign}(\sin\varphi_{i}))=(-1,1)$.

This equality and property (4.21) imply the following: for every $i=1,2$, the
vector $(1,-1)$ and the vector $\operatorname{\text{\bf Pr}}(a_{i},H)-a_{i}$
are co-directed. See Fig. 10.

Fig. 10: The half-planes $H_{1}$ and $H_{2}$ with the non-parallel boundaries:
the first case.

This proves that

$\operatorname{\text{\bf
Pr}}(a_{1},H)-a_{1}~{}~{}~{}\text{and}~{}~{}~{}\operatorname{\text{\bf
Pr}}(a_{2},H)-a_{2}~{}~{}~{}\text{are co-directed vectors}.$

Therefore, thanks to Lemma 4.7, (4.15) holds, and the proof of the lemma is
complete. $\blacksquare$

###### Lemma 4.11

Inequality (4.15) holds provided $\varphi_{1}\in(\pi/2,\pi)$ and
$\varphi_{2}\in(\pi,\varphi_{1}+\pi)$.

Proof. First, let us prove inequality (4.15) in the case
$\varphi_{1}\in(\pi/2,\pi)$ and
$\varphi_{2}\in\left(\pi,\tfrac{3}{2}\pi\right)$. See Fig. 11.

Fig. 11: The half-planes $H_{1}$ and $H_{2}$ with the non-parallel boundaries:
$\varphi_{2}\in\left(\pi,\tfrac{3}{2}\pi\right)$.

In this case, the following inequalities hold:

$\displaystyle\cos\varphi_{1}<0,~{}\sin\varphi_{1}>0,~{}\cos\varphi_{2}<0~{}~{}~{}\text{and}~{}~{}~{}\sin\varphi_{2}<0.$
(4.39)

Therefore, thanks to (4.21), the vector $\operatorname{\text{\bf
Pr}}(a_{1},H_{1})-a_{1}$ is co-directed with the vector $(1,-1)$, and the
vector $\operatorname{\text{\bf Pr}}(a_{2},H_{2})-a_{2}$ is co-directed with
$(1,1)$. Moreover, in this case the convex cone $H_{1}\cap H_{2}$ (with the
vertex $0$) contains the positive semi axis $Ox_{1}^{+}(=\\{(t,0):t\geq
0\\})$. This implies the following properties of the rectangular hulls of the
sets $S_{1}=H_{1}\cap(H_{2}+\delta Q_{0})$ and $S_{2}=H_{2}\cap(H_{1}+\delta
Q_{0})$:

${\mathcal{H}}[S_{1}]=\\{(u_{1},u_{2})\in{\bf R}^{2}:u_{1}\geq
s_{1}\\}~{}~{}~{}\text{and}~{}~{}~{}{\mathcal{H}}[S_{2}]=\\{(u_{1},u_{2})\in{\bf
R}^{2}:u_{1}\geq t_{1}\\}.$

We recall that $X_{1}=(s_{1},s_{2})$ and $X_{2}=(t_{1},t_{2})$. See (4.28) and
Fig. 10.

Let $\alpha_{i}\in(0,\pi/2)$, $i=1,2$, be the angle between the straight line
$\ell_{i}=\partial H_{i}$ and the axis $Ox_{1}$. On Fig. 10 we consider the
case $\alpha_{2}\leq\alpha_{1}$. We note that no necessity in the additional
consideration of the case $\alpha_{2}>\alpha_{1}$ because it can be obtained
from the case $\alpha_{2}<\alpha_{1}$ with the help of a suitable reflections
with respect to the coordinate axes and the bisectors of the coordinate
angles.

Let us prove that if $\alpha_{2}\leq\alpha_{1}$, then

$\displaystyle t_{1}\leq s_{1}\leq 0.$ (4.40)

First, let us note that, thanks to (4.33),
$\Delta=\sin(\varphi_{2}-\varphi_{1})>0$ (because
$\varphi_{2}-\varphi_{1}\in(0,\pi)$.) Also note that, thanks to (4.39),
$\sin\varphi_{1}>0$. Hence, thanks to formula (4.37), $s_{1}\leq 0$.

Let us see that

$\displaystyle
s_{1}-t_{1}=\frac{\delta}{\Delta}\sin(\varphi_{1}+\varphi_{2})=\frac{\delta}{\Delta}\sin(\alpha_{1}-\alpha_{2}).$
(4.41)

Indeed, thanks to (4.39),

$\|{\bf
h}_{1}\|_{1}=-\cos\varphi_{1}+\sin\varphi_{1}~{}~{}~{}\text{and}~{}~{}~{}\|{\bf
h}_{2}\|_{1}=-\cos\varphi_{2}-\sin\varphi_{2},$

so that, thanks to formulae (4.37) and (4.38),

$\displaystyle s_{1}-t_{1}$ $\displaystyle=$
$\displaystyle(\delta/\Delta)\\{-\|{\bf h}_{2}\|_{1}\sin\varphi_{1}-\|{\bf
h}_{1}\|_{1}\sin\varphi_{2}\\}$ $\displaystyle=$
$\displaystyle(\delta/\Delta)\\{-(-\cos\varphi_{2}-\sin\varphi_{2})\sin\varphi_{1}-(-\cos\varphi_{1}+\sin\varphi_{1})\sin\varphi_{2}\\}$
$\displaystyle=$
$\displaystyle(\delta/\Delta)\\{\cos\varphi_{2}\sin\varphi_{1}+\cos\varphi_{1}\sin\varphi_{2}\\}=(\delta/\Delta)\sin(\varphi_{1}+\varphi_{2}).$

We note that $\alpha_{1}=\varphi_{1}-\pi/2$ and
$\alpha_{2}=\tfrac{3}{2}\pi-\varphi_{2}$. Hence, we have

$\varphi_{1}+\varphi_{2}=\alpha_{1}-\alpha_{2}+2\pi$

proving (4.41). It remains to note that $\sin(\alpha_{1}-\alpha_{2})>0$
(because $0<\alpha_{2}\leq\alpha_{1}<\pi/2$) and $\Delta>0$ so that, thanks
(4.41), $t_{1}\leq s_{1}$ proving (4.40).

In particular, this inequality implies the inclusion
${\mathcal{H}}[S_{1}]\subset{\mathcal{H}}[S_{2}]$ as it shown on Fig. 10.
Furthermore, thanks to (4.25)

$\displaystyle a_{1}\notin H_{1}\cup
H_{2}~{}~{}~{}\text{and}~{}~{}~{}a_{1}\in{\mathcal{H}}[S_{1}]={\mathcal{H}}[H_{1}\cap(H_{2}+\delta
Q_{0})].$ (4.42)

Let $Y$ be the point of intersection of the line $\ell_{2}$ (the boundary of
$H_{2}$) and the line $\hat{\ell}$ passing through the point
$X_{1}=(s_{1},s_{2})$ and parallel to the axis $Ox_{2}$. (Thus,
$Y=(s_{1},y_{2})$ for some $y_{2}\in{\bf R}$). Recall that the point
$X_{2}=(t_{1},t_{2})$ lies on the line $\ell_{2}$, and, thanks to inequality
(4.40), $t_{1}\leq s_{1}\leq 0$. In particular, these observations shows that
$Y\in[X_{2},O]$ where $O=0$ is the origin.

Conditions (4.42) shows that the point $a_{1}$ belongs to the triangle
$\widetilde{T}=\Delta(X_{1},Y,O)$ with the vertices at the points $X_{1}$, $Y$
and $O$. Because $Y\in[X_{2},O]$, the triangle $\widetilde{T}$ is a subset of
the triangle $T=\Delta(X_{1},X_{2},O)$ with vertices at $X_{1}$, $X_{2}$ and
$O=0$. Hence, $a_{1}\in T$.

Let

$f(x)=\operatorname{dist}(x,H_{1})+\operatorname{dist}(x,H_{2}),~{}~{}~{}x\in
T.$

Prove that $f(x)\leq\delta$ on $T$. Indeed, $f$ is a convex continuous
function on $T$ so that its maximum is attained on the set of vertices of the
triangle $T$, i.e., at the points $O,X_{1}$ and $X$. But $f(O)=0$,
$f(X_{1})=\delta$ (because
$X_{1}\in\tilde{\ell}_{2}=\partial(H_{2}+\delta\,Q_{0})$) and
$f(X_{2})=\delta$ (because
$X_{2}\in\tilde{\ell}_{1}=\partial(H_{1}+\delta\,Q_{0})$). This proves the
required inequality $f(x)\leq\delta$, $x\in T$.

In particular,

$\displaystyle
f(a_{1})=\operatorname{dist}(a_{1},H_{1})+\operatorname{dist}(a_{1},H_{2})\leq\delta.$
(4.43)

Thus, condition (4.23) of Lemma 4.8 holds. Thanks to this lemma, inequality
(4.15) holds proving Lemma 4.11 for the angles $\varphi_{1}\in(\pi/2,\pi)$ and
$\varphi_{2}\in\left(\pi,\tfrac{3}{2}\pi\right)$.

Let us prove Lemma 4.11 for

$\displaystyle\varphi_{1}\in(\pi/2,\pi)~{}~{}~{}\text{and}~{}~{}~{}\varphi_{2}\in\left(\frac{3}{2}\,\pi,\varphi_{1}+\pi\right).~{}~{}~{}~{}~{}~{}\text{See
Fig. 12.}$ (4.44)

Fig. 12: The half-planes $H_{1}$ and $H_{2}$ with the non-parallel boundaries:
$\varphi_{2}\in\left(\frac{3}{2}\,\pi,\varphi_{1}+\pi\right)$.

In this case,

$\displaystyle\cos\varphi_{1}<0,~{}\sin\varphi_{1}>0,~{}\cos\varphi_{2}>0~{}~{}~{}\text{and}~{}~{}~{}\sin\varphi_{2}<0.$
(4.45)

Therefore, thanks to (4.21), the vector $\operatorname{\text{\bf
Pr}}(a_{1},H_{1})-a_{1}$ is co-directed with $(1,-1)$, and the vector
$\operatorname{\text{\bf Pr}}(a_{2},H_{2})-a_{2}$ is co-directed with
$(-1,1)$. Moreover,

${\mathcal{H}}[S_{1}]=\\{(u_{1},u_{2})\in{\bf R}^{2}:u_{1}\geq
s_{1},\,u_{2}\geq
s_{2}\\}~{}~{}~{}\text{and}~{}~{}~{}{\mathcal{H}}[S_{2}]=\\{(u_{1},u_{2})\in{\bf
R}^{2}:u_{1}\geq t_{1},\,u_{2}\geq t_{2}\\}.$

Let us prove that

$\displaystyle X_{1}-X_{2}=\delta(1,-1)$ (4.46)

$X_{1}=(s_{1},s_{2})$ and $X_{2}=(t_{1},t_{2})$ are the points defined by
(4.28). For explicit formulae for $s_{i},t_{i}$, $i=1,2$, see (4.37) and
(4.38).

Thanks to (4.45), we have

$\|{\bf
h}_{1}\|_{1}=|\cos\varphi_{1}|+|\sin\varphi_{1}|=-\cos\varphi_{1}+\sin\varphi_{1},~{}~{}~{}\|{\bf
h}_{2}\|_{1}=|\cos\varphi_{2}|+|\sin\varphi_{2}|=\cos\varphi_{2}-\sin\varphi_{2}.$

Therefore, thanks to (4.37) and (4.38),

$X_{1}=\frac{\delta}{\Delta}\,(\cos\varphi_{2}-\sin\varphi_{2})\,(-\sin\varphi_{1},\cos\varphi_{1})~{}~{}~{}\text{and}~{}~{}~{}X_{2}=\frac{\delta}{\Delta}\,(-\cos\varphi_{1}+\sin\varphi_{1})\,(\sin\varphi_{2},-\cos\varphi_{2}).$

Hence,

$\displaystyle X_{1}-X_{2}$ $\displaystyle=$
$\displaystyle\frac{\delta}{\Delta}\,((\cos\varphi_{2}-\sin\varphi_{2})\,(-\sin\varphi_{1})-(-\cos\varphi_{1}+\sin\varphi_{1})\sin\varphi_{2},$
$\displaystyle(\cos\varphi_{2}-\sin\varphi_{2})\cos\varphi_{1}-(-\cos\varphi_{1}+\sin\varphi_{1})(-\cos\varphi_{2}))$
$\displaystyle=$
$\displaystyle\frac{\delta}{\Delta}\,(-\cos\varphi_{2}\sin\varphi_{1}+\cos\varphi_{1}\sin\varphi_{2},-\sin\varphi_{2}\cos\varphi_{1}+\sin\varphi_{1}\cos\varphi_{2})$
$\displaystyle=$
$\displaystyle\frac{\delta}{\Delta}\sin(\varphi_{2}-\varphi_{1})(1,-1).$

Thanks to (4.33), $\Delta=\sin(\varphi_{2}-\varphi_{1})$, and the proof of
(4.46) is complete.

Thanks to this equality, $t_{1}=s_{1}-\delta$ and $t_{2}=s_{2}+\delta$.
Furthermore, (4.46) and (4.29) imply the following:

$S_{2}=S_{1}+\delta(-1,1)~{}~{}~{}\text{and}~{}~{}~{}{\mathcal{H}}[S_{2}]={\mathcal{H}}[S_{1}]+\delta(-1,1).$

Let us prove that

$\displaystyle t_{1}\leq s_{1}\leq
0~{}~{}~{}~{}\text{and}~{}~{}~{}~{}s_{2}\leq t_{2}\leq 0.$ (4.47)

In fact, we know that

$\varphi_{1}\in(\pi/2,\pi)~{}~{}~{}~{}\text{and}~{}~{}~{}~{}\varphi_{2}\in(\frac{3}{2}\,\pi,\varphi_{1}+\pi).$

Hence, $0<\varphi_{2}-\varphi_{1}<\pi$ proving that
$\Delta=\sin(\varphi_{2}-\varphi_{1})>0$. We also know that
$\sin\varphi_{1}>0$ so that, thanks to (4.36), $s_{1}\leq 0$. In addition,
$t_{1}=s_{1}-\delta\leq s_{1}$ proving the first inequality in (4.47).

Next, thanks to (4.38),

$t_{2}=-(\delta/\Delta)\,\|{\bf h}_{1}\|_{1}\,\cos\varphi_{2}.$

But $\Delta>0$ and $\cos\varphi_{2}>0$ so that $t_{2}\leq 0$. Moreover,
$s_{2}=t_{2}-\delta$, so that $s_{2}\leq t_{2}$, and the proof of (4.47) is
complete.

We recall that the point $a_{1}$ satisfies conditions (4.42). Therefore,

$a_{1}\in T=\Delta(X_{1},X_{2},O).$

See Fig. 12. From this and (4.43) it follows that condition (4.23) of Lemma
4.8 is satisfied. This lemma tells us that inequality (4.15) holds proving
Lemma 4.11 for the case (4.44).

The proof of Lemma 4.11 is complete. $\blacksquare$

Finally, the results of Lemmas 4.4 – 4.11 imply the required inequality (4.15)
completing the proof of Proposition 4.3. $\blacksquare$

We are in a position to complete the proof of Proposition 3.6.

Proof of inequality (3.27). Let us fix elements $x,y\in{\mathcal{M}}$. We set

$A_{1}=F^{[1]}[x:\tilde{\lambda}],~{}~{}~{}A_{2}=F^{[1]}[y:\tilde{\lambda}]$

and $a_{1}=g(x)$, $a_{2}=g(y)$. Recall that $g:{\mathcal{M}}\to{\bf R}$ is the
mapping satisfying (3.23) and (3.24).

We also recall that the mapping $F^{[1]}[\cdot:\tilde{\lambda}]$ is defined by
(3.4). Thus,

$\displaystyle A_{i}=\cap\\{A_{i}^{[u]}:u\in{\mathcal{M}}\\},~{}~{}i=1,2,$
(4.48)

where given $u\in{\mathcal{M}}$, we set

$\displaystyle
A_{1}^{[u]}=F(u)+\tilde{\lambda}\,\rho(u,x)Q_{0}~{}~{}~{}\text{and}~{}~{}~{}A_{2}^{[u]}=F(u)+\tilde{\lambda}\,\rho(u,y)Q_{0}.$
(4.49)

Lemma 3.3 tells us that each $A_{i}$, $i=1,2$, is a non-empty closed convex
subset of ${\bf R}^{2}$.

Thanks to inequality (3.24), we have

$\displaystyle\|a_{1}-a_{2}\|\leq\lambda\,\rho(x,y),$ (4.50)

and, thanks to (3.23),

$\displaystyle a_{i}\in{\mathcal{H}}[A_{i}]^{\operatorname{\bf
cl}},~{}~{}~{}i=1,2.$ (4.51)

Furthermore, formula (3.25) tells us that

$f(x)=\operatorname{\text{\bf
Pr}}(a_{1},A_{1})~{}~{}~{}~{}\text{and}~{}~{}~{}~{}f(y)=\operatorname{\text{\bf
Pr}}(a_{2},A_{2}).$

(We also recall that, thanks to Lemma 3.7, the metric projection
$\operatorname{\text{\bf Pr}}(a_{i},A_{i})$ is well defined, i.e.,
$\operatorname{\text{\bf Pr}}(a_{i},A_{i})$ is a singleton.)

In these settings, the required inequality (3.27) reads as follows:

$\displaystyle\|\operatorname{\text{\bf
Pr}}(a_{1},A_{1})-\operatorname{\text{\bf
Pr}}(a_{2},A_{2})\|\leq(2\lambda+\tilde{\lambda})\,\rho(x,y).$ (4.52)

Let us note that this inequality is immediate from (4.50) provided $a_{i}\in
A_{i}$, $i=1,2$, (because in this case $\operatorname{\text{\bf
Pr}}(a_{i},A_{i})=a_{i}$).

Suppose that either $a_{1}\notin A_{1}$ or $a_{2}\notin A_{2}$. Without loss
of generality, we may assume that $a_{1}\notin A_{1}$. Fix $\varepsilon>0$ and
prove that there exists a half-plane $H_{1}\in{\mathcal{H}}{\mathcal{P}}({\bf
R}^{2})$ such that

$\displaystyle H_{1}\supset
A_{1},~{}~{}~{}~{}H_{1}+\tilde{\lambda}\,\rho(x,y)Q_{0}\supset A_{2},$ (4.53)

and

$\displaystyle\|\operatorname{\text{\bf
Pr}}(a_{1},A_{1})-\operatorname{\text{\bf Pr}}(a_{1},H_{1})\|<\varepsilon.$
(4.54)

We construct the half-plane $H_{1}$ as follows: Because $a_{1}\notin A_{1}$,
we have $\operatorname{\text{\bf Pr}}(a_{1},A_{1})\neq a_{1}$ so that
$(\operatorname{\text{\bf Pr}}(a_{1},A_{1}),a_{1}]$ is a non-empty semi-open
interval in ${\bf R}^{2}$. Let us pick a point

$a^{(\varepsilon)}\in(\operatorname{\text{\bf Pr}}(a_{1},A_{1}),a_{1}]$

such that

$\displaystyle\|a^{(\varepsilon)}-\operatorname{\text{\bf
Pr}}(a_{1},A_{1})\|<\varepsilon.$ (4.55)

Because $\operatorname{\text{\bf Pr}}(a_{1},A_{1})$ is the nearest to $a_{1}$
point on $A_{1}$, we have

$(\operatorname{\text{\bf Pr}}(a_{1},A_{1}),a_{1}]\cap A_{1}=\emptyset.$

Therefore,

$a^{(\varepsilon)}\notin A_{1}=\cap\\{A_{1}^{[u]}:u\in{\mathcal{M}}\\}.$

See (4.48). This implies the existence of an element $u\in{\mathcal{M}}$ such
that $a^{(\varepsilon)}\notin A_{1}^{[u]}$. We let $B$ denote the set
$A_{1}^{[u]}$. Thus,

$\displaystyle a^{(\varepsilon)}\notin
B=A_{1}^{[u]}=F(u)+\tilde{\lambda}\,\rho(u,x)Q_{0}.$ (4.56)

See (4.49). Thanks to (4.51) and (4.48),

$\displaystyle a_{1}\in{\mathcal{H}}[A_{1}]^{\operatorname{\bf
cl}}~{}~{}~{}~{}\text{and}~{}~{}~{}~{}A_{1}\subset B.$ (4.57)

Therefore, thanks to Lemma 4.1, the metric projections
$\operatorname{\text{\bf Pr}}(a_{1},A_{1})$ and $\operatorname{\text{\bf
Pr}}(a_{1},B)$ are singletons such that

$\operatorname{\text{\bf Pr}}(a_{1},B)\in[\operatorname{\text{\bf
Pr}}(a_{1},A_{1}),a_{1}].$

See Fig. 13.

Fig. 13: Metric projections of $a_{1}$ onto $A_{1}$ and $B$.

We note that $\operatorname{\text{\bf Pr}}(a_{1},B)\in[\operatorname{\text{\bf
Pr}}(a_{1},A_{1}),a^{(\varepsilon)}]$; indeed, otherwise
$a^{(\varepsilon)}\in[\operatorname{\text{\bf
Pr}}(a_{1},A_{1}),\operatorname{\text{\bf Pr}}(a_{1},B)]\subset B$, a
contradiction. See (4.56). Hence, thanks to (4.55),

$\displaystyle\|\operatorname{\text{\bf
Pr}}(a_{1},A_{1})-\operatorname{\text{\bf
Pr}}(a_{1},B)\|\leq\|a^{(\varepsilon)}-\operatorname{\text{\bf
Pr}}(a_{1},A_{1})\|<\varepsilon.$ (4.58)

Let $\widetilde{Q}=Q(a_{1},r)$ where $r=\operatorname{dist}(a_{1},B)$. Thus,
$\widetilde{Q}\cap B=\\{\operatorname{\text{\bf Pr}}(a_{1},B)\\}$. Therefore,
thanks to the separation theorem, there exists a half-plane
$H_{1}\in{\mathcal{H}}{\mathcal{P}}({\bf R}^{2})$ which contains $B$ and
separates (not strictly) $\widetilde{Q}$ and $B$. Thus, $B\subset H_{1}$ and
$\widetilde{Q}\cap H_{1}=\operatorname{\text{\bf Pr}}(a_{1},B)$ as it shown on
Fig. 12. In particular, these properties imply the equality
$\operatorname{\text{\bf Pr}}(a_{1},H_{1})=\operatorname{\text{\bf
Pr}}(a_{1},B)$.

Let us see that inclusions (4.53) and inequality (4.54) hold for the half-
plane $H_{1}$. In fact, (4.54) is immediate from (4.58) and the last equality.

Prove (4.53). We know that $A_{1}\subset B$, see (4.57), so that $A_{1}\subset
B\subset H_{1}$. We also recall that $B=F(u)+\tilde{\lambda}\,\rho(u,x)Q_{0}$
(see (4.56)). Therefore,

$H_{1}+\tilde{\lambda}\,\rho(x,y)Q_{0}\supset
B+\tilde{\lambda}\,\rho(x,y)Q_{0}=F(u)+\tilde{\lambda}\,\rho(u,x)Q_{0}+\tilde{\lambda}\,\rho(x,y)Q_{0}=F(u)+\tilde{\lambda}\,(\rho(u,x)+\rho(x,y))\,Q_{0}.$

Therefore, thanks to the triangle inequality, (4.48) and (4.49), we have

$H_{1}+\tilde{\lambda}\,\rho(x,y)Q_{0}\supset
F(u)+\tilde{\lambda}\,\rho(u,y)\,Q_{0}=A_{2}^{[u]}\supset A_{2}$

proving (4.53).

Next, let us construct a half-plane $H_{2}\in{\mathcal{H}}{\mathcal{P}}({\bf
R}^{2})$ having the following properties:

$\displaystyle H_{2}\supset
A_{2},~{}~{}~{}~{}H_{2}+\tilde{\lambda}\,\rho(x,y)Q_{0}\supset A_{1},$ (4.59)

and

$\displaystyle\|\operatorname{\text{\bf
Pr}}(a_{2},A_{2})-\operatorname{\text{\bf Pr}}(a_{2},H_{2})\|<\varepsilon.$
(4.60)

If $a_{2}\notin A_{2}$, we define $H_{2}$ in the same way as we have defined
$H_{1}$ for $a_{1}$. In this case, properties (4.59), (4.60) are a complete
analog of properties (4.53) and (4.54) obtained for the point $a_{1}$.

If $a_{2}\in A_{2}$, we set

$H_{2}=H_{1}+\tilde{\lambda}\,\rho(x,y)Q_{0}.$

Clearly, $H_{2}$ is a half-plane. Let us see that inclusions (4.59) and
inequality (4.60) hold for this choice of $H_{2}$. Indeed, thanks to the
second inclusion in (4.53), we have $H_{2}\supset A_{2}$. In turn, thanks to
the first inclusion,

$H_{2}+\tilde{\lambda}\,\rho(x,y)Q_{0}=(H_{1}+\tilde{\lambda}\,\rho(x,y)Q_{0})+\tilde{\lambda}\,\rho(x,y)Q_{0}\supset
H_{1}\supset A_{1},$

proving (4.59). Finally, inequality (4.60) is trivial because
$\operatorname{\text{\bf Pr}}(a_{2},A_{2})=\operatorname{\text{\bf
Pr}}(a_{2},H_{2})(=a_{2})$. (Recall that $a_{2}\in A_{2}\subset H_{2}$.)

Now, we set

$\displaystyle\delta=\tilde{\lambda}\,\rho(x,y)+\varepsilon.$ (4.61)

Let us prove that the points $a_{1},a_{2}$ and the half-planes $H_{1}$ and
$H_{2}$ satisfy conditions (4.10), (4.13) and (4.14).

Thanks to (4.53), $H_{1}\supset A_{1}$, and, thanks to (4.59),
$H_{2}+\tilde{\lambda}\,\rho(x,y)Q_{0}\supset A_{1}$. Hence,

$H_{1}\cap(H_{2}+\tilde{\lambda}\,\rho(x,y)Q_{0})\supset A_{1}.$

Note that $\tilde{\lambda}\,\rho(x,y)<\delta$; see (4.61). Therefore,

$\displaystyle H_{1}\cap(H_{2}+\delta\,Q_{0})\supset A_{1}.$ (4.62)

We also know that $A_{1}\neq\emptyset$ so that
$H_{1}\cap(H_{2}+\delta\,Q_{0})\neq\emptyset$ as well. This proves that
$\operatorname{dist}(H_{1},H_{2})\leq\delta$ so that the condition (4.10) is
satisfied.

Let us prove that the points $a_{1}$ and $a_{2}$ satisfy condition (4.13).
Indeed, inclusion (4.62) tells us that

${\mathcal{H}}[A_{1}]\subset{\mathcal{H}}[H_{1}\cap(H_{2}+\delta\,Q_{0})].$

Clearly, the set ${\mathcal{H}}[H_{1}\cap(H_{2}+\delta\,Q_{0})]$ is closed (as
the rectangle hull of intersection of two half-planes). Hence,

${\mathcal{H}}[A_{1}]^{\operatorname{\bf
cl}}\subset{\mathcal{H}}[H_{1}\cap(H_{2}+\delta\,Q_{0})].$

But, thanks to (4.51), $a_{1}\in{\mathcal{H}}[A_{1}]^{\operatorname{\bf cl}}$
proving that $a_{1}\in{\mathcal{H}}[H_{1}\cap(H_{2}+\delta\,Q_{0})]$.

In the same fashion we show that
$a_{2}\in{\mathcal{H}}[H_{2}\cap(H_{1}+\delta\,Q_{0})]$ proving that condition
(4.13) holds.

Let us show that condition (4.14) is satisfied as well. Thanks to (4.59),

$\operatorname{\text{\bf Pr}}(a_{1},A_{1})\in A_{1}\subset
H_{2}+\tilde{\lambda}\,\rho(x,y)\,Q_{0},$

and, thanks to (4.54),

$\operatorname{\text{\bf Pr}}(a_{1},H_{1})\in\operatorname{\text{\bf
Pr}}(a_{1},A_{1})+\varepsilon\,Q_{0}\subset A_{1}+\varepsilon\,Q_{0}.$

Therefore, thanks to (4.61),

$\operatorname{\text{\bf Pr}}(a_{1},H_{1})\in
A_{1}+\varepsilon\,Q_{0}\subset(H_{2}+\tilde{\lambda}\,\rho(x,y)\,Q_{0})+\varepsilon\,Q_{0}=H_{2}+\delta\,Q_{0}.$

In the same way we show that $\operatorname{\text{\bf Pr}}(a_{2},H_{2})\in
H_{1}+\delta\,Q_{0}$ completing the proof of (4.14).

Therefore, thanks to Proposition 4.3, inequality (4.15) holds. This inequality
together with (4.50) and (4.61) imply the following:

$\|\operatorname{\text{\bf Pr}}(a_{1},H_{1})-\operatorname{\text{\bf
Pr}}(a_{2},H_{2})\|\leq 2\|a_{1}-a_{2}\|+\delta\leq
2\lambda\,\rho(x,y)+\tilde{\lambda}\,\rho(x,y)+\varepsilon.$

From this, (4.54) and (4.60), we have

$\displaystyle\|\operatorname{\text{\bf
Pr}}(a_{1},A_{1})-\operatorname{\text{\bf Pr}}(a_{2},A_{2})\|$
$\displaystyle\leq$ $\displaystyle\|\operatorname{\text{\bf
Pr}}(a_{1},A_{1})-\operatorname{\text{\bf
Pr}}(a_{1},H_{1})\|+\|\operatorname{\text{\bf
Pr}}(a_{1},H_{1})-\operatorname{\text{\bf Pr}}(a_{2},H_{2})\|$
$\displaystyle+$ $\displaystyle\|\operatorname{\text{\bf
Pr}}(a_{2},H_{2})-\operatorname{\text{\bf
Pr}}(a_{2},A_{2})\|\leq(2\lambda+\tilde{\lambda})\,\rho(x,y)+3\varepsilon.$

Since $\varepsilon>0$ is arbitrary, this implies (4.52) proving the required
inequality (3.27) and completing the proof of Proposition 3.6. $\blacksquare$

Finally, combining part (i) of Proposition 3.5 with Proposition 3.6, we obtain
the statement of Theorem 3.2. $\blacksquare$

##  5\. Lipschitz selection criteria in the two dimensional case.

5.1 Constructive criteria for Lipschitz selections: proofs.

We begin with the proof of Theorem 1.10. This proof is based on the following
result.

###### Proposition 5.1

Let ${\mathfrak{M}}=({\mathcal{M}},\rho)$ be a pseudometric space, and let
$F:{\mathcal{M}}\to\operatorname{Conv}({\bf R}^{2})$ be a set-valued mapping.
Given constants $\tilde{\lambda}$ and $\lambda$,
$0\leq\lambda\leq\tilde{\lambda}$, let us assume that

$\displaystyle{\mathcal{R}}_{F}[x,x^{\prime}:\tilde{\lambda}]\cap\left\\{{\mathcal{R}}_{F}[y,y^{\prime}:\tilde{\lambda}]+\lambda\,\rho(x,y)\,Q_{0}\right\\}\neq\emptyset~{}~{}~{}\text{for
every}~{}~{}~{}x,x^{\prime},y,y^{\prime}\in{\mathcal{M}}.$ (5.1)

Then for every
$x,x^{\prime},x^{\prime\prime},y,y^{\prime},y^{\prime\prime}\in{\mathcal{M}}$,
the following property

${\mathcal{W}}_{F}[x,x^{\prime},x^{\prime\prime}:3\tilde{\lambda}]\cap\left\\{{\mathcal{W}}_{F}[y,y^{\prime},y^{\prime\prime}:3\tilde{\lambda}]+\lambda\,\rho(x,y)Q_{0}\right\\}\neq\emptyset$

holds.

Proof. Clearly, property (5.1) guarantees that the rectangle
${\mathcal{R}}_{F}[x,y:\tilde{\lambda}]\neq\emptyset$ for every
$x,y\in{\mathcal{M}}$.

Let $y,y^{\prime},y^{\prime\prime}\in{\mathcal{M}}$. Clearly,
${\mathcal{W}}_{F}[y,y^{\prime},y^{\prime\prime}:\tilde{\lambda}]={\mathcal{W}}_{F}[y,y^{\prime\prime},y^{\prime}:\tilde{\lambda}]$,
see (3.1), so that, without loss of generality, we may assume that
$\rho(y,y^{\prime})\leq\rho(y,y^{\prime\prime})$. Thanks to the triangle
inequality, we have

$\rho(y^{\prime},y^{\prime\prime})\leq\rho(y,y^{\prime})+\rho(y,y^{\prime\prime})\leq
2\rho(y,y^{\prime\prime})~{}~{}~{}~{}\text{so
that}~{}~{}~{}~{}~{}\rho(y,y^{\prime})+\rho(y^{\prime},y^{\prime\prime})\leq
3\rho(y,y^{\prime\prime}).$

Hence,

$\displaystyle{\mathcal{W}}_{F}[y,y^{\prime},y^{\prime\prime}:3\tilde{\lambda}]$
$\displaystyle=$
$\displaystyle{\mathcal{H}}[\\{F(y^{\prime})+3\tilde{\lambda}\,\rho(y,y^{\prime})\,Q_{0}\\}\cap\\{F(y^{\prime\prime})+3\tilde{\lambda},\rho(y,y^{\prime\prime})\,Q_{0}\\}]$
$\displaystyle\supset$
$\displaystyle{\mathcal{H}}[\\{F(y^{\prime})+\tilde{\lambda}\,\rho(y,y^{\prime})\,Q_{0}\\}\cap\\{(F(y^{\prime\prime})+\tilde{\lambda}\,\rho(y^{\prime},y^{\prime\prime})Q_{0})+\tilde{\lambda}\,\rho(y,y^{\prime})Q_{0}\\}].$

Clearly, for every $A,B\subset{\bf R}^{2}$, $A\cap B\neq\emptyset$, and every
$r\geq 0$, the following inclusion

$A\cap B+rQ_{0}\subset(A+rQ_{0})\cap(B+rQ_{0})$

holds. From this, property (2.14) and inequality $\lambda\leq\tilde{\lambda}$,
we have

$\displaystyle{\mathcal{W}}_{F}[y,y^{\prime},y^{\prime\prime}:3\tilde{\lambda}]$
$\displaystyle\supset$
$\displaystyle{\mathcal{H}}[F(y^{\prime})\cap\\{F(y^{\prime\prime})+\tilde{\lambda}\,\rho(y^{\prime},y^{\prime\prime})Q_{0}\\}+\tilde{\lambda}\,\rho(y,y^{\prime})Q_{0}]$
$\displaystyle=$
$\displaystyle{\mathcal{H}}[F(y^{\prime})\cap\\{F(y^{\prime\prime})+\tilde{\lambda}\,\rho(y^{\prime},y^{\prime\prime})Q_{0}\\}]+\tilde{\lambda}\,\rho(y,y^{\prime})Q_{0}$
$\displaystyle\supset$
$\displaystyle{\mathcal{H}}[F(y^{\prime})\cap\\{F(y^{\prime\prime})+\tilde{\lambda}\,\rho(y^{\prime},y^{\prime\prime})Q_{0}\\}]+\lambda\,\rho(y,y^{\prime})Q_{0}.$

This and definition (1.17) imply the following inclusion:

$\displaystyle{\mathcal{W}}_{F}[y,y^{\prime},y^{\prime\prime}:3\tilde{\lambda}]\supset{\mathcal{R}}_{F}[y^{\prime},y^{\prime\prime}:\tilde{\lambda}]+\lambda\,\rho(y,y^{\prime})Q_{0}.$
(5.2)

Now, let us consider elements
$x,x^{\prime},x^{\prime\prime},y,y^{\prime},y^{\prime\prime}\in{\mathcal{M}}$.
We may assume that $\rho(x,x^{\prime})\leq\rho(x,x^{\prime\prime})$ and
$\rho(y,y^{\prime})\leq\rho(y,y^{\prime\prime})$. We know that in this case
(5.2) holds. In the same way we prove that

${\mathcal{W}}_{F}[x,x^{\prime},x^{\prime\prime}:3\tilde{\lambda}]\supset{\mathcal{R}}_{F}[x^{\prime},x^{\prime\prime}:\tilde{\lambda}]+\lambda\,\rho(x,x^{\prime})Q_{0}.$

From this inclusion, (5.2) and the triangle inequality, we have

$\displaystyle{\mathcal{A}}$ $\displaystyle=$
$\displaystyle{\mathcal{W}}_{F}[x,x^{\prime},x^{\prime\prime}:3\tilde{\lambda}]\cap\\{{\mathcal{W}}_{F}[y,y^{\prime},y^{\prime\prime}:3\tilde{\lambda}]+\lambda\,\rho(x,y)Q_{0}\\}$
$\displaystyle\supset$
$\displaystyle\\{{\mathcal{R}}_{F}[x^{\prime},x^{\prime\prime}:\tilde{\lambda}]+\lambda\,\rho(x,x^{\prime})Q_{0}\\}\cap\\{{\mathcal{R}}_{F}[y^{\prime},y^{\prime\prime}:\tilde{\lambda}]+\lambda\,\rho(y,y^{\prime})Q_{0}+\lambda\,\rho(x,y)Q_{0}\\}$
$\displaystyle\supset$
$\displaystyle{\mathcal{B}}=\\{{\mathcal{R}}_{F}[x^{\prime},x^{\prime\prime}:\tilde{\lambda}]+\lambda\,\rho(x,x^{\prime})Q_{0}\\}\cap\\{{\mathcal{R}}_{F}[y^{\prime},y^{\prime\prime}:\tilde{\lambda}]+\lambda\,\rho(x,y^{\prime})Q_{0}\\}.$

Thanks to (5.1),

${\mathcal{R}}_{F}[x^{\prime},x^{\prime\prime}:\tilde{\lambda}]\cap\\{{\mathcal{R}}_{F}[y^{\prime},y^{\prime\prime}:\tilde{\lambda}]+\lambda\,\rho(x^{\prime},y^{\prime})\,Q_{0}\\}\neq\emptyset$

so that there exists points
$p_{1}\in{\mathcal{R}}_{F}[x^{\prime},x^{\prime\prime}:\tilde{\lambda}]$ and
$p_{2}\in{\mathcal{R}}_{F}[y^{\prime},y^{\prime\prime}:\tilde{\lambda}]$ such
that $\|p_{1}-p_{2}\|\leq\lambda\,\rho(x^{\prime},y^{\prime})$. Therefore,
thanks to the triangle inequality,

$\|p_{1}-p_{2}\|\leq\lambda\,\rho(x^{\prime},y^{\prime})\leq\lambda\,\rho(x,x^{\prime})+\lambda\,\rho(x,y^{\prime}).$

This inequality implies the existence of a point $w\in[p_{1},p_{2}]$ such that
$\|p_{1}-w\|\leq\lambda\,\rho(x,x^{\prime})$ and
$\|p_{2}-w\|\leq\lambda\,\rho(x,y^{\prime})$. Therefore,
$w\in{\mathcal{B}}\subset{\mathcal{A}}$, and the proof of the proposition is
complete. $\blacksquare$

Proof of Theorem 1.10. The necessity part of Theorem 1.10 and inequality
$\inf\lambda\leq\,|F|_{{\mathfrak{M}}}$ are immediate from part (i) of
Proposition 3.1.

Let us prove the sufficiency part. Thanks to Proposition 5.1, condition (1.18)
of Theorem 1.10 implies condition (3.3) of Theorem 3.2 with
$\tilde{\lambda}=3\lambda$.

Theorem 3.2 tells us that there exists a Lipschitz selection $f$ of $F$ with

$\|f\|_{\operatorname{Lip}({\mathcal{M}})}\leq
2\lambda+\tilde{\lambda}=2\lambda+3\lambda=5\lambda.$

This proves the sufficiency and inequality $|F|_{{\mathfrak{M}}}\leq
5\inf\lambda$.

The proof of Theorem 1.10 is complete. $\blacksquare$

###### Theorem 5.2

Let $({\mathcal{M}},\rho)$ be a pseudometric space, and let
$F:{\mathcal{M}}\to\operatorname{Conv}({\bf R}^{2})$ be a set-valued mapping.
Suppose that ${\mathfrak{M}}$ and $F$ satisfy Condition 1.9.

The mapping $F$ has a Lipschitz selection if and only if there exists a
constant $\lambda\geq 0$ such that for every subset
${\mathcal{M}}^{\prime}\subset{\mathcal{M}}$ consisting of at most $N=4$
points, the restriction $F|_{{\mathcal{M}}^{\prime}}$ of $F$ to
${\mathcal{M}}^{\prime}$ has a Lipschitz selection
$f_{{\mathcal{M}}^{\prime}}$ with Lipschitz seminorm
$\|f_{{\mathcal{M}}^{\prime}}\|_{\operatorname{Lip}({\mathcal{M}}^{\prime})}\leq\lambda$.

Furthermore, $\inf\lambda\leq\,|F|_{{\mathfrak{M}}}\leq\gamma\inf\lambda$ with
$\gamma=3$.

Proof. The necessity part of the theorem and the inequality
$\inf\lambda\leq\,|F|_{{\mathfrak{M}}}$ are obvious. Let us prove the
sufficiency.

Suppose that there exist a constant $\lambda\geq 0$ such that for every subset
${\mathcal{M}}^{\prime}\subset{\mathcal{M}}$ with
$\\#{\mathcal{M}}^{\prime}\leq 4$, the restriction
$F|_{{\mathcal{M}}^{\prime}}$ of $F$ to ${\mathcal{M}}^{\prime}$ has a
Lipschitz selection $f_{{\mathcal{M}}^{\prime}}$ with Lipschitz seminorm
$\|f_{{\mathcal{M}}^{\prime}}\|_{\operatorname{Lip}({\mathcal{M}}^{\prime})}\leq\lambda$.
Our goal is to prove the existence of a selection $f$ of $F$ with
$\|f\|_{\operatorname{Lip}({\mathcal{M}})}\leq 3\lambda$.

Let us show that condition (3.3) of Theorem 3.2 is satisfied with
$\tilde{\lambda}=\lambda$.

Let
$x,x^{\prime},x^{\prime\prime},y,y^{\prime},y^{\prime\prime}\in{\mathcal{M}}$,
and let
${\mathcal{M}}^{\prime}=\\{x^{\prime},x^{\prime\prime},y^{\prime},y^{\prime\prime}\\}$.
We know that the restriction $F|_{{\mathcal{M}}^{\prime}}$ of $F$ to
${\mathcal{M}}^{\prime}$ has a Lipschitz selection
$f_{{\mathcal{M}}^{\prime}}$ with
$\|f_{{\mathcal{M}}^{\prime}}\|_{\operatorname{Lip}({\mathcal{M}}^{\prime})}\leq\lambda$.
Thus,

$f_{{\mathcal{M}}^{\prime}}(x^{\prime})\in
F(x^{\prime}),~{}f_{{\mathcal{M}}^{\prime}}(x^{\prime\prime})\in
F(x^{\prime\prime}),~{}f_{{\mathcal{M}}^{\prime}}(y^{\prime})\in
F(y^{\prime})~{}~{}~{}\text{and}~{}~{}~{}f_{{\mathcal{M}}^{\prime}}(y^{\prime\prime})\in
F(y^{\prime\prime}).$

It is well known that any Lipschitz mapping from a closed subset of a
pseudometric space $({\mathcal{M}},\rho)$ into $\ell^{2}_{\infty}$ (i.e.,
${\bf R}^{2}$ equipped with the uniform norm) can be extended to all of the
space $({\mathcal{M}},\rho)$ with preserving the Lipschitz constant. Let
$\tilde{f}:{\mathcal{M}}\to{\bf R}^{2}$ be such an extension of the mapping
$f_{{\mathcal{M}}^{\prime}}$ from ${\mathcal{M}}^{\prime}$ to ${\mathcal{M}}$.
Thus, $\tilde{f}|_{{\mathcal{M}}^{\prime}}=f_{{\mathcal{M}}^{\prime}}$ and
$\|\tilde{f}\|_{\operatorname{Lip}({\mathcal{M}})}=\|f_{{\mathcal{M}}^{\prime}}\|_{\operatorname{Lip}({\mathcal{M}}^{\prime})}\leq\lambda$
so that the following inequalities hold:

$\|f_{{\mathcal{M}}^{\prime}}(x^{\prime})-\tilde{f}(x)\|=\|\tilde{f}(x^{\prime})-\tilde{f}(x)\|\leq\lambda\,\rho(x,x^{\prime}),~{}~{}~{}~{}~{}~{}\|f_{{\mathcal{M}}^{\prime}}(x^{\prime\prime})-\tilde{f}(x)\|=\|\tilde{f}(x^{\prime\prime})-\tilde{f}(x)\|\leq\lambda\,\rho(x,x^{\prime\prime}),$

and

$\|f_{{\mathcal{M}}^{\prime}}(y^{\prime})-\tilde{f}(y)\|=\|\tilde{f}(y^{\prime})-\tilde{f}(y)\|\leq\lambda\,\rho(y,y^{\prime}),~{}~{}~{}~{}~{}~{}\|f_{{\mathcal{M}}^{\prime}}(y^{\prime\prime})-\tilde{f}(y)\|=\|\tilde{f}(y^{\prime\prime})-\tilde{f}(y)\|\leq\lambda\,\rho(y,y^{\prime\prime}).$

Hence,

$\tilde{f}(x)\in\\{F(x^{\prime})+\lambda\,\rho(x^{\prime},x)\,Q_{0}\\}\cap\\{F(x^{\prime\prime})+\lambda\,\rho(x^{\prime\prime},x)\,Q_{0}\\}$

and

$\tilde{f}(y)\in\\{F(y^{\prime})+\lambda\,\rho(y^{\prime},y)\,Q_{0}\\}\cap\\{F(y^{\prime\prime})+\lambda\,\rho(y^{\prime\prime},y)\,Q_{0}\\}$

so that
$\tilde{f}(x)\in{\mathcal{W}}_{F}[x,x^{\prime},x^{\prime\prime}:\lambda]$ and
$\tilde{f}(y)\in{\mathcal{W}}_{F}[y,y^{\prime},y^{\prime\prime}:\lambda]$, see
(3.1).

Furthermore, because
$\|\tilde{f}\|_{\operatorname{Lip}({\mathcal{M}})}\leq\lambda$, we have
$\|\tilde{f}(x)-\tilde{f}(y)\|\leq\lambda\,\rho(x,y)$. Hence,

$\tilde{f}(x)\in{\mathcal{W}}_{F}[x,x^{\prime},x^{\prime\prime}:\tilde{\lambda}]\cap\\{{\mathcal{W}}_{F}[y,y^{\prime},y^{\prime\prime}:\tilde{\lambda}]+\lambda\,\rho(x,y)\,Q_{0}\\}$

proving that condition (3.3) of Theorem 3.2 holds. Thanks to this theorem, $F$
has a Lipschitz selection $f:{\mathcal{M}}\to{\bf R}^{2}$ with
$\|f\|_{\operatorname{Lip}({\mathcal{M}})}\leq
2\lambda+\tilde{\lambda}=3\lambda$, and the proof of Theorem 5.2 is complete.
$\blacksquare$

###### Remark 5.3

We have proved Theorem 5.2 for the Banach space $\ell^{2}_{\infty}=({\bf
R}^{2},\|\cdot\|)$, i.e., ${\bf R}^{2}$ equipped with the uniform norm
$\|\cdot\|$. Let us consider a slightly more general version of Theorem 5.2
for a Banach space $X=({\bf R}^{2},\|\cdot\|_{X})$ supplied with a certain
Banach norm $\|\cdot\|_{X}$.

Let $B_{X}$ be the unit ball $X$. According to a result of E. Asplund [3],
$B_{X}$ contains a parallelogram $P$ centered at $(0,0)$ which expanded by
$\frac{3}{2}$ will cover $B_{X}$. Since the Banach space $X_{P}$ with the unit
ball $P$ is linearly isometric to $\ell^{2}_{\infty}$, we conclude that an
analog of Theorem 5.2 holds for an arbitrary Banach space $X$ with the
constant $\frac{3}{2}\cdot 3\lambda=4.5\lambda$ (instead of $3\lambda$ as for
$\ell^{2}_{\infty}$). $\blacktriangleleft$

Combining Theorem 3.2 with the part (ii) of Proposition 3.1, we obtain the
following criterion for Lipschitz selections.

###### Theorem 5.4

Let ${\mathfrak{M}}=({\mathcal{M}},\rho)$ be a pseudometric space, and let
$F:{\mathcal{M}}\to\operatorname{Conv}({\bf R}^{2})$ be a set-valued mapping
satisfying Condition 1.9.

The mapping $F$ has a Lipschitz selection if and only if there exists a
constant $\lambda\geq 0$ such that for every
$x,x^{\prime},x^{\prime\prime},y,y^{\prime},y^{\prime\prime}\in{\mathcal{M}}$,
we have

$\displaystyle{\mathcal{W}}_{F}[x,x^{\prime},x^{\prime\prime}:\lambda]\cap\\{{\mathcal{W}}_{F}[y,y^{\prime},y^{\prime\prime}:\lambda]+\lambda\,\rho(x,y)\,Q_{0}\\}\neq\emptyset.$
(5.3)

Furthermore, the following inequality holds:

$\displaystyle\inf\lambda\leq\,|F|_{{\mathfrak{M}}}\leq 3\inf\lambda.$ (5.4)

Comparing this result with Theorem 1.10, we note that Theorem 5.4 provides
better upper bound for $|F|_{{\mathfrak{M}}}$ ($3\inf\lambda$ in (5.4) rather
than $5\inf\lambda$ as in inequality (1.19)). The price of such a refinement
is as follows: property (5.3) exploits rectangles
${\mathcal{W}}_{F}[\cdot,\cdot,\cdot:\lambda]$ each of these depend on three
arbitrary elements of ${\mathcal{M}}$. In turn, condition (1.18) of Theorem
1.10 formulates in terms of rectangles
${\mathcal{R}}_{F}[\cdot,\cdot:\lambda]$ each depending only on two elements
of ${\mathcal{M}}$. In other words, in the criterion of Theorem 5.4, we use
more information about geometric properties of the set-valued mapping $F$,
and, as a result, obtain better estimates for the Lipschitz seminorm of its
Lipschitz selection.

5.2 Criteria for Lipschitz selections in terms of intersections of sets.

In this section we prove two constructive Lipschitz selection criteria
formulated in terms of intersections of certain families of rectangles in
${\bf R}^{2}$. We begin with a Lipschitz selection criterion of such a kind
for mappings taking values in the family ${\mathfrak{R}}({\bf R}^{2})$ of all
rectangles in ${\bf R}^{2}$ with sides parallel to the coordinate axes.

###### Proposition 5.5

Let ${\mathcal{T}}:{\mathcal{M}}\to{\mathcal{R}}({\bf R}^{2})$ be a set-valued
mapping. Let us assume that either ${\mathcal{M}}$ is finite or all rectangles
${\mathcal{T}}(x)$, $x\in{\mathcal{M}}$, are closed and at least one of them
is bounded.

Then ${\mathcal{T}}$ has a Lipschitz selection if and only if there exists a
constant $\lambda\geq 0$ such that the set

$\displaystyle{\mathcal{T}}^{[1]}[x:\lambda]=\bigcap_{z\in{\mathcal{M}}}\,\left[{\mathcal{T}}(z)+\lambda\,\rho(x,z)\,Q_{0}\right]$
(5.5)

is non-empty for every $x\in{\mathcal{M}}$. Furthermore,

$|{\mathcal{T}}|_{{\mathfrak{M}}}=\inf\\{\lambda:{\mathcal{T}}^{[1]}[x:\lambda]\neq\emptyset~{}~{}~{}\text{for
all}~{}~{}~{}x\in{\mathcal{M}}\\}.$

Proof. (Necessity.) Suppose that ${\mathcal{T}}$ has a Lipschitz selection
$\tau:{\mathcal{M}}\to{\mathfrak{R}}({\bf R}^{2})$ with
$\|\tau\|_{\operatorname{Lip}({\mathcal{M}})}\leq\lambda$. Then, given
$x\in{\mathcal{M}}$, we have $\|\tau(x)-\tau(z)\|\leq\lambda\,\rho(x,z)$ for
every $z\in{\mathcal{M}}$. But $\tau(x)\in{\mathcal{T}}(x)$ and
$\tau(z)\in{\mathcal{T}}(z)$ (because $\tau$ is a selection of
${\mathcal{T}}$) so that $\tau(x)\in{\mathcal{T}}(z)+\lambda\,\rho(x,z)Q_{0}$.
Therefore, thanks to (5.5), $\tau(x)\in{\mathcal{T}}^{[1]}[x:\lambda]$ proving
the necessity.

(Sufficiency.) Suppose that ${\mathcal{T}}^{[1]}[x:\lambda]\neq\emptyset$ for
every $x\in{\mathcal{M}}$. Then, thanks to definition (5.5),
${\mathcal{T}}(x)\cap[{\mathcal{T}}(z)+\lambda\,\rho(x,z)\,Q_{0}]\neq\emptyset$
for every $x,z\in{\mathcal{M}}$, proving the existence of points
$\tilde{\tau}(x)\in{\mathcal{T}}(x)$, $\tilde{\tau}(z)\in{\mathcal{T}}(z)$
such that $\|\tilde{\tau}(x)-\tilde{\tau}(z)\|\leq\lambda\,\rho(x,z)$. This
property and the assumption of the proposition’s hypothesis enables us to
apply Proposition 2.10 to the set-valued mapping ${\mathcal{T}}$. This
proposition tells us that ${\mathcal{T}}$ has a Lipschitz selection
$\tau:{\mathcal{M}}\to{\bf R}^{2}$ with
$\|\tau\|_{\operatorname{Lip}({\mathcal{M}})}\leq\eta$ completing the proof of
the proposition. $\blacksquare$

The following theorem is the main result of this section.

###### Theorem 5.6

Suppose that a pseudometric space ${\mathfrak{M}}=({\mathcal{M}},\rho)$ and a
set-valued mapping $F:{\mathcal{M}}\to\operatorname{Conv}({\bf R}^{2})$
satisfy Condition 1.9.

Then $F$ has a Lipschitz selection if and only if there exists a constant
$\lambda\geq 0$ such that

$\displaystyle\bigcap_{y,y^{\prime}\in{\mathcal{M}}}\left\\{\,{\mathcal{R}}_{F}[y,y^{\prime}:\lambda]+\lambda\,\rho(x,y)Q_{0}\right\\}\neq\emptyset~{}~{}~{}~{}~{}~{}\text{for
every}~{}~{}x\in{\mathcal{M}}.$ (5.6)

Moreover, in this case, $\inf\lambda\leq\,|F|_{{\mathfrak{M}}}\leq
5\inf\lambda$.

Proof. (Necessity). Let $f:{\mathcal{M}}\to{\bf R}^{2}$ be a Lipschitz
selection of $F$, and let $\lambda=\|f\|_{\operatorname{Lip}({\mathcal{M}})}$.
Then for every $x,y,y^{\prime}\in{\mathcal{M}}$ the following is true:
$f(x)\in F(x),f(y)\in F(y)$, $f(y^{\prime})\in F(y^{\prime})$,

$\|f(x)-f(y)\|\leq\lambda\,\rho(x,y)~{}~{}~{}\text{and}~{}~{}~{}\|f(y)-f(y^{\prime})\|\leq\lambda\,\rho(y,y^{\prime}).$

Hence, $f(y)\in F(y)\cap[F(y^{\prime})+\lambda\,\rho(y,y^{\prime})Q_{0}]$ and
$f(x)\in f(y)+\lambda\,\rho(x,y)Q_{0},$ proving that

$f(x)\in(F(y)\cap[F(y^{\prime})+\lambda\,\rho(y,y^{\prime})Q_{0}])+\lambda\,\rho(x,y)Q_{0}~{}~{}~{}~{}\text{
for all}~{}~{}~{}~{}y,y^{\prime}\in{\mathcal{M}}.$

Clearly,

$\displaystyle(F(y)\cap\\{F(y^{\prime})+\lambda\,\rho(y^{\prime},y)Q_{0}\\})+\lambda\,\rho(x,y)Q_{0}$
$\displaystyle\subset$
$\displaystyle{\mathcal{H}}[F(y)\cap\\{F(y^{\prime})+\lambda\,\rho(y^{\prime},y)Q_{0}\\}]+\lambda\,\rho(x,y)Q_{0}$
$\displaystyle=$
$\displaystyle{\mathcal{R}}_{F}[y,y^{\prime}:\lambda]+\lambda\,\rho(x,y)Q_{0}$

so that
$f(x)\in{\mathcal{R}}_{F}[y,y^{\prime}:\lambda]+\lambda\,\rho(x,y)Q_{0}$ for
every $y,y^{\prime}\in{\mathcal{M}}$.

This property implies (5.6) and inequality
$\inf\lambda\leq\,|F|_{{\mathfrak{M}}}$ completing the proof of the necessity.

(Sufficiency.) We assume that property (5.6) holds. Thanks to this property,

${\mathcal{R}}_{F}[x,x^{\prime}:\lambda]\cap\\{{\mathcal{R}}_{F}[y,y^{\prime}:\lambda]+\lambda\,\rho(x,y)\,Q_{0}\\}\neq\emptyset$

for every $x,x^{\prime},y,y^{\prime}\in{\mathcal{M}}$ proving that condition
(1.18) of Theorem 1.10 holds. This theorem tells us that $F$ has a Lipschitz
selection with Lipschitz seminorm at most $5\lambda$. This proves the
inequality $|F|_{{\mathfrak{M}}}\leq 5\inf\lambda$ and completes the proof of
Theorem 5.6. $\blacksquare$

###### Remark 5.7

We note that, thanks to representation (2.12), property (5.6) is equivalent to
the following one: for every $x\in{\mathcal{M}}$ and and every $i=1,2$, the
set

$\bigcap_{y,y^{\prime}\in{\mathcal{M}}}\operatorname{\text{\sc
Pr}}_{i}[\left\\{F(y)\cap(F(y^{\prime})+\lambda\,\rho(y,y^{\prime})Q_{0})\right\\}+\lambda\,\rho(x,y)Q_{0}]\neq\emptyset.$

We recall that $\operatorname{\text{\sc Pr}}_{i}$ denotes the operator of the
orthogonal projection onto the axis $Ox_{i}$. $\blacktriangleleft$

##  6\. Projection Algorithm for nearly optimal Lipschitz selections.

In this section we present a number of nearly optimal algorithms for Lipschitz
selections based on the geometrical construction suggested in the proof of
Theorem 3.2. We refer to these algorithms as the “Projection Algorithms”.

6.1 The $\vec{\lambda}$-Projection Algorithm.

Let ${\mathfrak{M}}=({\mathcal{M}},\rho)$ be a pseudometric space, and let
$F:{\mathcal{M}}\to\operatorname{Conv}({\bf R}^{2})$ be a set-valued mapping.
Given a constant $\lambda\geq 0$ we define a set-valued mapping
$F^{[1]}[\cdot:\lambda]$ on ${\mathcal{M}}$ by letting

$\displaystyle
F^{[1]}[x:\lambda]=\bigcap_{y\in{\mathcal{M}}}\,\left[F(y)+\lambda\,\rho(x,y)\,Q_{0}\right],~{}~{}~{}~{}x\in{\mathcal{M}}.$
(6.1)

We refer to the mapping $F^{[1]}[\cdot:\lambda]$ as the $\lambda$-balanced
refinement of $F$. (This important object was introduced in [18] and [34]. We
have already met various variants of it in (2.35), (2.43), (3.4), (3.15) and
(5.5).)

###### The Projection Algorithm 6.1

Given a vector $\vec{\lambda}=(\lambda_{1},\lambda_{2})$ with non-negative
coordinates $\lambda_{1},\lambda_{2}\geq 0$, a pseudometric space
${\mathfrak{M}}=({\mathcal{M}},\rho)$, and a set-valued mapping
$F:{\mathcal{M}}\to\operatorname{Conv}({\bf R}^{2})$, the Projection Algorithm
either produces a selection $f_{\vec{\lambda};F}$ of $F$ (the outcome
“Success”) or stops (the outcome “No go”). This procedure includes the
following five main steps.

STEP 1. At this step we construct the $\lambda_{1}$-balanced refinement of
$F$, i.e., the set-valued mapping

$\displaystyle
F^{[1]}[x:\lambda_{1}]=\bigcap_{y\in{\mathcal{M}}}\,\left[F(y)+\lambda_{1}\,\rho(x,y)\,Q_{0}\right].$
(6.2)

If $F^{[1]}[x:\lambda_{1}]=\emptyset$ for some $x\in{\mathcal{M}}$, the
algorithm produces the outcome “No go” and stops.

STEP 2. Let us assume that the above condition does not hold, i.e., for every
element $x\in{\mathcal{M}}$ the $\lambda_{1}$-balanced refinement
$F^{[1]}[x:\lambda_{1}]$ is non-empty.

In this case, for each $x\in{\mathcal{M}}$, we construct the rectangular hull
of $F^{[1]}[x:\lambda_{1}]$, the set

$\displaystyle{\mathcal{T}}_{F,\lambda_{1}}(x)={\mathcal{H}}[F^{[1]}[x:\lambda_{1}]].$
(6.3)

Thus, ${\mathcal{T}}_{F,\lambda_{1}}$ is a set-valued mapping which maps
${\mathcal{M}}$ into the family ${\mathfrak{R}}({\bf R}^{2})$ of all
rectangles in ${\bf R}^{2}$. See Fig. 14.

Fig. 14: The second step of the Projection Algorithm.

STEP 3. For every $x\in{\mathcal{M}}$, we construct the $\lambda_{2}$-balanced
refinement of the mapping ${\mathcal{T}}_{F,\lambda_{1}}$, i.e., the rectangle
${\mathcal{T}}^{[1]}_{F,\lambda_{1}}[x:\lambda_{2}]$ defined by

$\displaystyle{\mathcal{T}}^{[1]}_{F,\lambda_{1}}[x:\lambda_{2}]=\bigcap_{y\in{\mathcal{M}}}\,\left[{\mathcal{T}}_{F,\lambda_{1}}(y)+\lambda_{2}\,\rho(x,y)\,Q_{0}\right].$
(6.4)

See Fig. 15.

Fig. 15: The third step of the Projection Algorithm.

If

$\displaystyle{\mathcal{T}}^{[1]}_{F,\lambda_{1}}[x:\lambda_{2}]=\emptyset~{}~{}~{}~{}\text{for
some}~{}~{}~{}x\in{\mathcal{M}},$ (6.5)

the algorithm produces the outcome “No go” and stops.

STEP 4. At this step, we assume that for each $x\in{\mathcal{M}}$ the
rectangle ${\mathcal{T}}^{[1]}_{F,\lambda_{1}}[x:\lambda_{2}]\neq\emptyset$.
We let ${\mathcal{T}}^{[1]}_{F,\lambda_{1}}[x:\lambda_{2}]^{\operatorname{\bf
cl}}$ denote the closure of the rectangle
${\mathcal{T}}^{[1]}_{F,\lambda_{1}}[x:\lambda_{2}]\neq\emptyset$.

Let $O=(0,0)$ be the origin. We define a mapping $g_{F}:{\mathcal{M}}\to{\bf
R}^{2}$ by letting

$\displaystyle g_{F}(x)=\operatorname{center}\left(\operatorname{\text{\sc
Pr}}\left(O,{\mathcal{T}}^{[1]}_{F,\lambda_{1}}[x:\lambda_{2}]^{\operatorname{\bf
cl}}\right)\right),~{}~{}~{}~{}~{}~{}x\in{\mathcal{M}}.\hskip 51.21495pt$
(6.6)

See Fig. 16.

Fig. 16: The mapping $g_{F}:{\mathcal{M}}\to{\bf R}^{2}$, a selection of the
set-valued mapping ${\mathcal{T}}_{F,\lambda_{1}}^{\operatorname{\bf cl}}$.

We recall that $\operatorname{\text{\bf Pr}}(\cdot,S)$ denotes the operator of
metric projection onto a closed convex subset $S\subset{\bf R}^{2}$, see
(2.6), and $\operatorname{center}\,(\cdot)$ denotes the center of a centrally
symmetric bounded set in ${\bf R}^{2}$.

STEP 5. We define the mapping $f_{\vec{\lambda};F}:{\mathcal{M}}\to{\bf
R}^{2}$ by letting

$\displaystyle f_{\vec{\lambda};F}(x)=\operatorname{\text{\bf
Pr}}(g(x),F^{[1]}[x:\lambda_{1}]),~{}~{}~{}~{}~{}~{}x\in{\mathcal{M}}.$ (6.7)

See Fig. 17.

Fig. 17: The final step of the Projection Algorithm.

At this stage, the algorithm produces the outcome “Success” and stops.
$\blacksquare$

To specify the dependence on the parameters $\lambda_{1}$ and $\lambda_{2}$,
we refer to the above algorithm as the $\vec{\lambda}$-Projection Algorithm
($\vec{\lambda}$-PA for short).

###### Remark 6.2

We note that the $(\lambda_{1},\lambda_{2})$-Projection Algorithm produces the
outcome “Success” if and only if the following conditions are satisfied:

$\displaystyle
F^{[1]}[x:\lambda_{1}]\neq\emptyset~{}~{}~{}\text{and}~{}~{}~{}{\mathcal{T}}^{[1]}_{F,\lambda_{1}}[x:\lambda_{2}]\neq\emptyset~{}~{}~{}~{}\text{for
every}~{}~{}~{}x\in{\mathcal{M}}.$ (6.8)

Indeed, this algorithm does not stop at STEP 1 which is equivalent to the
first condition in (6.8). Also, the algorithm does not stop at STEP 3 which,
thanks to (6.5), is equivalent to the second condition in (6.8).
$\blacktriangleleft$

The next theorem describes the main properties of the $\vec{\lambda}$-PA.

###### Theorem 6.3

Let $\lambda_{1},\lambda_{2}\geq 0$, and let
$\vec{\lambda}=(\lambda_{1},\lambda_{2})$. Let
${\mathfrak{M}}=({\mathcal{M}},\rho)$ be a pseudometric space, and let
$F:{\mathcal{M}}\to\operatorname{Conv}({\bf R}^{2})$ be a set-valued mapping.
Suppose that ${\mathfrak{M}}$ and $F$ satisfy Condition 1.9.

If $\vec{\lambda}$-Projection Algorithm produces the outcome “No go” (see STEP
1 and STEP 3), then we guarantee that there does not exist a Lipschitz
selection of $F$ with Lipschitz seminorm at most
$\min\\{\lambda_{1},\lambda_{2}\\}$.

Otherwise, the $\vec{\lambda}$-Projection Algorithm produces the outcome
“Success” (see STEP 5) and returns the mapping
$f_{\vec{\lambda};F}:{\mathcal{M}}\to{\bf R}^{2}$ defined by formula (6.7).
This mapping has the following properties:

($\bigstar A$) The mapping $f_{\vec{\lambda};F}$ is well defined. This means
the following: (a) for every $x\in{\mathcal{M}}$, the set
$F^{[1]}[x:\lambda_{1}]\neq\emptyset$ and the rectangle
${\mathcal{T}}^{[1]}_{F,\lambda_{1}}[x:\lambda_{2}]\neq\emptyset$ (see (6.4)),
(b) the mapping $g_{F}$ (see (6.6)) is well defined, and (c) the metric
projection defined by the right hand side of (6.7) is a singleton.

($\bigstar B$) $f_{\vec{\lambda};F}$ is a Lipschitz selection of $F$ with the
Lipschitz seminorm

$\|f_{\lambda;F}\|_{\operatorname{Lip}({\mathcal{M}})}\leq\lambda_{1}+2\lambda_{2}.$

Proof. Let us see that whenever the $\vec{\lambda}$-PA produces the outcomes
“No go” there does not exist a Lipschitz selection of $F$ with Lipschitz
seminorm at most $\lambda^{\min}=\min\\{\lambda_{1},\lambda_{2}\\}$.

Indeed, suppose that $F$ has a Lipschitz selection $f:{\mathcal{M}}\to{\bf
R}^{2}$ with $\|f\|_{\operatorname{Lip}({\mathcal{M}})}\leq\lambda^{\min}$.
Then, $f(x)\in F(x)$ for every $x\in{\mathcal{M}}$ and

$\|f(x)-f(y)\|\leq\lambda^{\min}\,\rho(x,y)~{}~{}~{}~{}\text{for
all}~{}~{}~{}~{}x,y\in{\mathcal{M}}.$

Hence,

$f(x)\in F(y)+\lambda^{\min}\,\rho(x,y)Q_{0}~{}~{}~{}\text{for
every}~{}~{}~{}y\in{\mathcal{M}}.$

Therefore, thanks to definition (6.1), we have

$f(x)\in F^{[1]}[x:\lambda^{\min}]\subset
F^{[1]}[x:\lambda_{1}]~{}~{}~{}~{}\text{for
every}~{}~{}~{}~{}x\in{\mathcal{M}}.$

Furthermore, from this and (6.3), we have
$f(x)\in{\mathcal{T}}_{F,\lambda_{1}}(x)$, $x\in{\mathcal{M}}$, proving that
$f$ is a Lipschitz selection of the set-valued mapping
${\mathcal{T}}_{F,\lambda_{1}}$ with
$\|f\|_{\operatorname{Lip}({\mathcal{M}})}\leq\lambda^{\min}$.

Repeating the above argument for ${\mathcal{T}}_{F,\lambda_{1}}$ rather than
for $F$, we conclude that

$f(x)\in{\mathcal{T}}^{[1]}_{F,\lambda_{1}}[x:\lambda^{\min}]\subset{\mathcal{T}}^{[1]}_{F,\lambda_{1}}[x:\lambda_{2}]~{}~{}~{}~{}\text{for
every}~{}~{}~{}~{}x\in{\mathcal{M}}.$

See (6.4). Thus, if there exists $x\in{\mathcal{M}}$ such that

$F^{[1]}[x:\lambda_{1}]=\emptyset~{}~{}~{}~{}~{}\text{(the outcome {\bf``No
go''} at {\bf STEP 1})}$

or

${\mathcal{T}}^{[1]}_{F,\lambda_{1}}[x:\lambda_{2}]=\emptyset~{}~{}~{}~{}~{}\text{(the
outcome {\bf``No go''} at {\bf STEP 3})},$

we can guarantee that there does not exist a Lipschitz selection of $F$ with
Lipschitz seminorm $\leq\lambda^{\min}$.

Next, let us assume that the $\lambda$-PA produces the outcome “Success” (see
STEP 5). Then, thanks to Remark 6.2, the set-valued mapping $F$ satisfies
condition (6.8).

Let us prove property ($\bigstar A$). Clearly, the part (a) is immediate from
(6.8). To prove part (b), we note that metric projection of the origin $O$
onto the rectangle
${\mathcal{T}}^{[1]}_{F,\lambda_{1}}[x:\lambda_{2}]^{\operatorname{\bf cl}}$
is either a singleton or a closed line segment. Therefore, $g_{F}$ is well
defined on ${\mathcal{M}}$ (because the set $\operatorname{\text{\bf
Pr}}(O,{\mathcal{T}}^{[1]}_{F,\lambda_{1}}[x:\lambda_{2}])$ is a non-empty
bounded centrally symmetric set). See formula (6.6).

Let us prove part (c). Thanks to (6.3) and (6.4),

$\displaystyle
g_{F}(x)\in{\mathcal{T}}^{[1]}_{F,\lambda_{1}}[x:\lambda_{2}]^{\operatorname{\bf
cl}}\subset{\mathcal{T}}_{F,\lambda_{1}}^{\operatorname{\bf
cl}}(x)={\mathcal{H}}[F^{[1]}[x:\lambda_{1}]]^{\operatorname{\bf cl}}.$ (6.9)

(To prove the inclusion “$\subset$” in (6.9) put $y=x$ in (6.4).) Therefore,
thanks to Lemma 3.7 and definition (6.6), $f_{\vec{\lambda};F}(x)$, the metric
projection of $g_{F}(x)$ onto $F^{[1]}[x:\lambda_{1}]$, see (6.7), is a
singleton. The proof of property ($\bigstar A$) is complete.

Let us prove property ($\bigstar B$) of the theorem. We will follow the scheme
of the proof of the sufficiency part of the key Theorem 3.2 for the special
case

$\displaystyle\tilde{\lambda}=\lambda_{1}~{}~{}~{}~{}\text{and}~{}~{}~{}~{}\lambda=\lambda_{2}.$
(6.10)

Thanks to (6.8),
${\mathcal{T}}^{[1]}_{F,\tilde{\lambda}}[x:\lambda]\neq\emptyset$ for every
$x\in{\mathcal{M}}$. Part (a) of Proposition 2.7 tells us that in this case
the set-valued mapping
${\mathcal{T}}^{[1]}_{F,\tilde{\lambda}}[\cdot:\lambda]$ is Lipschitz with
respect to the Hausdorff distance, i.e.,

$\displaystyle\operatorname{d_{H}}\left({\mathcal{T}}^{[1]}_{F,\tilde{\lambda}}[x:\lambda],{\mathcal{T}}^{[1]}_{F,\tilde{\lambda}}[y:\lambda]\right)\leq\lambda\,\rho(x,y)~{}~{}~{}\text{for
all}~{}~{}~{}x,y\in{\mathcal{M}}.$ (6.11)

It is clear that for every two rectangles $S_{1},S_{2}\in{\mathfrak{R}}({\bf
R}^{2})$ we have
$\operatorname{d_{H}}(S_{1},S_{2})=\operatorname{d_{H}}(S_{1}^{\operatorname{\bf
cl}},S_{2}^{\operatorname{\bf cl}})$, so that, thanks to (6.11),

$\displaystyle\operatorname{d_{H}}\left({\mathcal{T}}^{[1]}_{F,\tilde{\lambda}}[x:\lambda]^{\operatorname{\bf
cl}},{\mathcal{T}}^{[1]}_{F,\tilde{\lambda}}[y:\lambda]^{\operatorname{\bf
cl}}\right)\leq\lambda\,\rho(x,y)~{}~{}~{}\text{for
every}~{}~{}~{}x,y\in{\mathcal{M}}.$ (6.12)

Let
$\delta(x)=\operatorname{dist}(0,{\mathcal{T}}^{[1]}_{F,\tilde{\lambda}}[x:\lambda])$.
Clearly,
$\delta(x)=\operatorname{dist}(0,{\mathcal{T}}^{[1]}_{F,\tilde{\lambda}}[x:\lambda]^{\operatorname{\bf
cl}})$. Then,

$|\delta(x)-\delta(y)|=|\operatorname{dist}(0,{\mathcal{T}}^{[1]}_{F,\tilde{\lambda}}[x:\lambda])-\operatorname{dist}(0,{\mathcal{T}}^{[1]}_{F,\tilde{\lambda}}[y:\lambda])|\leq\operatorname{d_{H}}\left({\mathcal{T}}^{[1]}_{F,\tilde{\lambda}}[x:\lambda],{\mathcal{T}}^{[1]}_{F,\tilde{\lambda}}[y:\lambda]\right)$

proving that

$\displaystyle|\delta(x)-\delta(y)|\leq\lambda\,\rho(x,y)~{}~{}~{}\text{for
every}~{}~{}~{}x,y\in{\mathcal{M}}.$ (6.13)

We note that

$\operatorname{\text{\bf
Pr}}(O,{\mathcal{T}}^{[1]}_{F,\tilde{\lambda}}[x:\lambda]^{\operatorname{\bf
cl}})=Q(O,\delta(x))\cap{\mathcal{T}}^{[1]}_{F,\tilde{\lambda}}[x:\lambda]^{\operatorname{\bf
cl}}.$

From this and Lemma 2.4, we have

$\displaystyle\operatorname{\text{\bf
Pr}}(O,{\mathcal{T}}^{[1]}_{F,\tilde{\lambda}}[x:\lambda]^{\operatorname{\bf
cl}})+\lambda\,\rho(x,y)Q_{0}$ $\displaystyle=$
$\displaystyle\\{Q(O,\delta(x))+\lambda\,\rho(x,y)Q_{0}\\}\cap\\{{\mathcal{T}}^{[1]}_{F,\tilde{\lambda}}[x:\lambda]^{\operatorname{\bf
cl}}+\lambda\,\rho(x,y)Q_{0}\\}$ $\displaystyle=$ $\displaystyle
Q(O,\delta(x)+\lambda\,\rho(x,y))\cap\\{{\mathcal{T}}^{[1]}_{F,\tilde{\lambda}}[x:\lambda]^{\operatorname{\bf
cl}}+\lambda\,\rho(x,y)Q_{0}\\}.$

Note that, thanks to (6.13), $\delta(y)\leq\delta(x)+\lambda\,\rho(x,y)$, and,
thanks to (6.12),

${\mathcal{T}}^{[1]}_{F,\tilde{\lambda}}[y:\lambda]^{\operatorname{\bf
cl}}\subset\
{\mathcal{T}}^{[1]}_{F,\tilde{\lambda}}[x:\lambda]^{\operatorname{\bf
cl}}+\lambda\,\rho(x,y)Q_{0}.$

Hence,

$\operatorname{\text{\bf
Pr}}(O,{\mathcal{T}}^{[1]}_{F,\tilde{\lambda}}[x:\lambda]^{\operatorname{\bf
cl}})+\lambda\,\rho(x,y)Q_{0}\supset
Q(O,\delta(y))\cap{\mathcal{T}}^{[1]}_{F,\tilde{\lambda}}[y:\lambda]^{\operatorname{\bf
cl}}=\operatorname{\text{\bf
Pr}}(O,{\mathcal{T}}^{[1]}_{F,\tilde{\lambda}}[y:\lambda]^{\operatorname{\bf
cl}}).$

By interchanging the roles of $x$ and $y$, we obtain also

$\operatorname{\text{\bf
Pr}}(O,{\mathcal{T}}^{[1]}_{F,\tilde{\lambda}}[y:\lambda]^{\operatorname{\bf
cl}})+\lambda\,\rho(x,y)Q_{0}\supset\operatorname{\text{\bf
Pr}}(O,{\mathcal{T}}^{[1]}_{F,\tilde{\lambda}}[y:\lambda]^{\operatorname{\bf
cl}}).$

These two inclusions imply the inequality

$\displaystyle\operatorname{d_{H}}\left(\operatorname{\text{\bf
Pr}}(O,{\mathcal{T}}^{[1]}_{F,\tilde{\lambda}}[x:\lambda]^{\operatorname{\bf
cl}}),\operatorname{\text{\bf
Pr}}(O,{\mathcal{T}}^{[1]}_{F,\tilde{\lambda}}[y:\lambda]^{\operatorname{\bf
cl}})\right)\leq\lambda\,\rho(x,y),~{}~{}~{}~{}x,y\in{\mathcal{M}}.$ (6.14)

As we have noted above, the set $\operatorname{\text{\bf
Pr}}(O,{\mathcal{T}}^{[1]}_{F,\tilde{\lambda}}[x:\lambda])$ is either a
singleton or a closed line segment. This line segment lies on one of the sides
of the square $Q(O,\delta(x))$, proving that the metric projection
$\operatorname{\text{\bf
Pr}}(O,{\mathcal{T}}^{[1]}_{F,\tilde{\lambda}}[x:\lambda]^{\operatorname{\bf
cl}})$ is a bounded rectangle, i.e., an element of the family
${\mathfrak{R}}({\bf R}^{2})$. Therefore, thanks to part (ii) of Claim 2.6 and
(6.14), the mapping $g_{F}$ defined by formula (6.6) is Lipschitz with
Lipschitz seminorm at most $\lambda$.

Let us also not that, thanks to (6.9) and (6.10), for every
$x\in{\mathcal{M}}$, we have

$g_{F}(x)\in{\mathcal{T}}_{F,\tilde{\lambda}}^{\operatorname{\bf
cl}}(x)={\mathcal{H}}[F^{[1]}[x:\tilde{\lambda}]]^{\operatorname{\bf cl}}.$

These properties of $g_{F}$ show that the mapping $g=g_{F}$ satisfies
conditions (3.23) and (3.24).

Furthermore, comparing (3.25) with (6.7), we conclude that
$f=f_{\vec{\lambda};F}$ where $f$ is the mapping defined by the formula
(3.25). Proposition 3.6 tells us that this mapping is a selection of $F$ with
Lipschitz seminorm

$\|f\|_{\operatorname{Lip}({\mathcal{M}})}=\|f_{\vec{\lambda};F}\|_{\operatorname{Lip}({\mathcal{M}})}\leq\tilde{\lambda}+2\lambda=\lambda_{1}+2\lambda_{2}.$

The proof of Theorem 6.3 is complete. $\blacksquare$

###### Remark 6.4

Theorem 6.3 holds for various versions of the $\vec{\lambda}$-Projection
Algorithm related to the specific choice of the mapping $g_{F}$ at STEP 4 of
the algorithm. The proof of Theorem 6.3 shows that $g_{F}$ should be a
Lipschitz selection of the set-valued mapping

${\mathcal{T}}_{F,\lambda_{1}}^{\operatorname{\bf
cl}}(x)={\mathcal{H}}[F^{[1]}[\cdot:\lambda_{1}]]^{\operatorname{\bf
cl}}~{}~{}~{}~{}\text{with}~{}~{}~{}~{}\|g_{F}\|_{\operatorname{Lip}({\mathcal{M}})}\leq\lambda_{2},$

i.e., $g_{F}$ have to satisfy condition (3.23) and inequality (3.24) with
constants $\tilde{\lambda}=\lambda_{1}$ and $\lambda=\lambda_{2}$.

Let us note some of these versions.

(i) We can define $g_{F}(x)$ by formula (6.6) with replacing the origin $O$ by
an arbitrary point in ${\bf R}^{2}$;

(ii) Suppose that

$\displaystyle\text{for every}~{}~{}x\in{\mathcal{M}}~{}~{}\text{the
set}~{}~{}F^{[1]}[x:\lambda_{1}]~{}~{}\text{is bounded}.$ (6.15)

Then the rectangle ${\mathcal{T}}^{[1]}_{F,\lambda_{1}}[x:\lambda_{2}]$,
(i.e., the rectangular hull of $F^{[1]}[x:\lambda_{1}]$) is also bounded for
all $x\in{\mathcal{M}}$. In this case, we can define $g_{F}$ by the formula

$\displaystyle
g_{F}(x)=\operatorname{center}\left({\mathcal{T}}^{[1]}_{F,\lambda_{1}}[x:\lambda_{2}]\right),~{}~{}~{}~{}~{}x\in{\mathcal{M}}.$
(6.16)

See Fig. 18.

Fig. 18: STEP 4 of the Projection Algorithm: the case of bounded sets
$F^{[1]}[x:\lambda_{1}]$.

Then, thanks to part (iii) of Proposition 3.5, $g_{F}$ is Lipschitz with
$\|g_{F}\|_{\operatorname{Lip}({\mathcal{M}})}\leq\lambda_{2}$. Thus, for this
choice of $g_{F}$ both property (3.23) and inequality (3.24) hold.

We note that, thanks to Lemma 3.3, property (6.15) holds provided the set
${\mathcal{M}}$ is infinite, so that in this case we can define $g_{F}$ by
formula (6.16).

Of course, if ${\mathcal{M}}$ is finite, we can not guarantee that property
(6.15) holds. However, in this case, the following property of the rectangles
$\\{{\mathcal{T}}^{[1]}_{F,\lambda_{1}}[x:\lambda_{2}]:x\in{\mathcal{M}}\\}$
maybe useful: if one of the rectangles of this family is a bounded set, then
all rectangles from this family are bounded as well, i.e., (6.15) holds. This
property is immediate from the fact that at STEP 4 the mapping
${\mathcal{T}}^{[1]}_{F,\lambda_{1}}[\cdot:\lambda_{2}]$ is Lipschitz with
respect to the Hausdorff distance. See inequality (6.11). (Recall that
$\lambda=\lambda_{2}$.)

(iii) Suppose that there exists $r>0$ such that, for every
$x\in{\mathcal{M}}$, the intersection of the square $Q(O,r)$ and the rectangle
${\mathcal{T}}^{[1]}_{F,\lambda_{1}}[x:\lambda_{2}]$ is non-empty. (For
instance, such $r$ exists provided the set ${\mathcal{M}}$ is finite.) In this
case, we can define $g_{F}$ by the formula

$g_{F}(x)=\operatorname{center}\left({\mathcal{T}}^{[1]}_{F,\lambda_{1}}[x:\lambda_{2}]^{\operatorname{\bf
cl}}\cap Q(O,r)\right),~{}~{}~{}~{}~{}x\in{\mathcal{M}}.$

Clearly,

$g_{F}(x)\in{\mathcal{T}}^{[1]}_{F,\lambda_{1}}[x:\lambda_{2}]^{\operatorname{\bf
cl}}\subset{\mathcal{T}}_{F,\lambda_{1}}^{\operatorname{\bf
cl}}(x)~{}~{}~{}\text{on}~{}~{}{\mathcal{M}}$

so that property (3.23) holds. The proof of (3.24) in this case follows the
same scheme as the proof of this inequality for $g_{F}$ defined by formula
(6.6). $\blacktriangleleft$

6.2 Projection Algorithms and a solution to the second main problem.

We are in a position to present a solution to Problem 1.2, the second main
problem of the paper.

Let ${\mathfrak{M}}=({\mathcal{M}},\rho)$ be a pseudometric space, and let
$F:{\mathcal{M}}\to\operatorname{Conv}({\bf R}^{2})$ be a set-valued mapping.

###### Definition 6.5

Let

$\displaystyle{\mathcal{L}}_{{\mathcal{R}}}(F)=\\{\lambda\geq
0:{\mathcal{R}}_{F}[x,x^{\prime}:\lambda]\cap\\{{\mathcal{R}}_{F}[y,y^{\prime}:\lambda]+\lambda\,\rho(x,y)\,Q_{0}\\}\neq\emptyset~{}\,\text{for
all}~{}x,x^{\prime},y,y^{\prime}\in{\mathcal{M}}\\}.$ (6.17)

We set

$\displaystyle\Lambda_{{\mathcal{R}}}(F)=\inf{\mathcal{L}}_{{\mathcal{R}}}(F)$
(6.18)

provided ${\mathcal{L}}_{{\mathcal{R}}}(F)\neq\emptyset$, and
$\Lambda_{{\mathcal{R}}}(F)=+\infty$ if
${\mathcal{L}}_{{\mathcal{R}},T}(F)=\emptyset$. $\blacktriangleleft$

Thus, $\Lambda_{{\mathcal{R}}}(F)$ is the infimum of constants $\lambda\geq 0$
such that condition (1.18) of Theorem 1.10 is satisfied. Hence, thanks to the
necessity part of Theorem 1.10 and (1.19), we have

$\displaystyle\Lambda_{{\mathcal{R}}}(F)\leq\,|F|_{{\mathfrak{M}}}.$ (6.19)

Let us prove the following useful property of the constant
$\Lambda_{{\mathcal{R}}}(F)$.

###### Lemma 6.6

Let ${\mathfrak{M}}=({\mathcal{M}},\rho)$ be a pseudometric space. Suppose
that either $F:{\mathcal{M}}\to{\mathcal{K}}({\bf R}^{2})$ or
$F:{\mathcal{M}}\to{\mathcal{H}}{\mathcal{P}}({\bf R}^{2})$, see (1.3) and
(1.4). If $\Lambda_{{\mathcal{R}}}(F)<\infty$, then the infimum in the right
hand side of definition (6.18) is attained. In other words, in these settings,
condition (1.18) of Theorem 1.10 is satisfied with
$\lambda=\Lambda_{{\mathcal{R}}}(F)$.

Proof. Let $T=(x,x^{\prime},y,y^{\prime})\subset{\mathcal{M}}$ be an (ordered)
quadruple of elements of ${\mathcal{M}}$, and let

${\mathcal{L}}_{{\mathcal{R}},T}(F)=\\{\lambda\geq
0:{\mathcal{R}}_{F}[x,x^{\prime}:\lambda]\cap\\{{\mathcal{R}}_{F}[y,y^{\prime}:\lambda]+\lambda\,\rho(x,y)\,Q_{0}\\}\neq\emptyset\\}.$

Let

$\displaystyle\Lambda_{{\mathcal{R}},T}(F)=\inf{\mathcal{L}}_{{\mathcal{R}},T}(F)$
(6.20)

provided ${\mathcal{L}}_{{\mathcal{R}},T}(F)\neq\emptyset$, and
$\Lambda_{{\mathcal{R}},T}(F)=+\infty$ if
${\mathcal{L}}_{{\mathcal{R}},T}(F)=\emptyset$.

Clearly, thanks to Definition 6.5 and (6.20),

$\displaystyle\Lambda_{{\mathcal{R}}}(F)=\sup\Lambda_{{\mathcal{R}},T}(F)$
(6.21)

where the supremum is taken over all (ordered) quadruples
$T=(x,x^{\prime},y,y^{\prime})\subset{\mathcal{M}}$.

Let us prove that the infimum in the right hand side of (6.20) is attained,
i.e., for each (ordered) quadruple $T=(x,x^{\prime},y,y^{\prime})$ of elements
of ${\mathcal{M}}$, we have

$\displaystyle{\mathcal{R}}_{F}[x,x^{\prime}:\lambda]\cap\\{{\mathcal{R}}_{F}[y,y^{\prime}:\lambda]+\lambda\,\rho(x,y)\,Q_{0}\\}\neq\emptyset~{}~{}~{}~{}\text{for
every}~{}~{}~{}\lambda\geq\Lambda_{{\mathcal{R}},T}(F).$ (6.22)

Let us note that if this property is true, then the proof of the lemma is
immediate. Indeed, thanks to (6.21),
$\Lambda_{{\mathcal{R}},T}(F)\leq\Lambda_{{\mathcal{R}}}(F)$ for every $T$, so
that, thanks to (6.22), for every $x,x^{\prime},y,y^{\prime}\in{\mathcal{M}}$,
we have

${\mathcal{R}}_{F}[x,x^{\prime}:\lambda]\cap\\{{\mathcal{R}}_{F}[y,y^{\prime}:\lambda]+\lambda\,\rho(x,y)\,Q_{0}\\}\neq\emptyset~{}~{}~{}~{}\text{with}~{}~{}~{}\lambda=\Lambda_{{\mathcal{R}}}(F)$

proving the lemma.

We turn to the proof of property (6.22). Thanks to part (i) of Remark 1.11,
the quantity

$\displaystyle\Lambda_{{\mathcal{R}},T}(F)=\inf\lambda$ (6.23)

where the infimum is taken over all constants $\lambda\geq 0$ such that for
every $i=1,2$, there exist points

$\displaystyle A(i)=(a_{1}(i),a_{2}(i))\in F(x),~{}~{}A^{\prime}(i)\in
F(x^{\prime}),~{}~{}B(i)=(b_{1}(i),b_{2}(i))\in F(y),~{}~{}B^{\prime}(i)\in
F(y^{\prime})$ (6.24)

satisfying the following inequalities:

$\displaystyle\|A(i)-A^{\prime}(i)\|\leq\lambda\rho(x,x^{\prime}),~{}~{}~{}\|B(i)-B^{\prime}(i)\|\leq\lambda\rho(y,y^{\prime})~{}~{}\text{and}~{}~{}|a_{i}(i)-b_{i}(i)|\leq\lambda\rho(x,y).$
(6.25)

Furthermore, property (6.22) holds provided the infimum in the right hand side
of (6.23) is attained.

Let us prove this property. We know that $\Lambda_{{\mathcal{R}}}(F)$ is
finite, i.e., $\Lambda_{{\mathcal{R}}}(F)\leq\lambda_{0}$ for some
$\lambda_{0}\geq 0$. Therefore, thanks to (6.21),
$\Lambda_{{\mathcal{R}},T}(F)\leq\lambda_{0}$ as well. Thus, without loss of
generality, we can assume that in (6.23) we have
$0\leq\lambda\leq\lambda_{0}$. Furthermore, this observation and Definition
6.5 imply the existence of a constant $\lambda$ and points $A(i)$,
$A^{\prime}(i)$, $B(i)$, $B^{\prime}(i)$ satisfying this inequality and
constraints (6.24) and (6.25).

Our aim is to show that under all these conditions, the infimum in (6.23) is
attained. To this end, let us consider a tuple

${\mathcal{T}}=(\lambda,A(1),A^{\prime}(1),B(1),B^{\prime}(1),A(2),A^{\prime}(2),B(2),B^{\prime}(2))$

where $A(i)=(a_{1}(i),a_{2}(i))$,
$A^{\prime}(i)=(a^{\prime}_{1}(i),a^{\prime}_{2}(i))$,
$B(i)=(b_{1}(i),b_{2}(i))$,
$B^{\prime}(i)=(b^{\prime}_{1}(i),b^{\prime}_{2}(i))$, $i=1,2$, are points in
${\bf R}^{2}$. Because ${\mathcal{T}}$ depends on $17$ parameters, we will
identify this tuple with a point in ${\bf R}^{17}$. Then the constrains
(6.24), (6.25) and the inequality $0\leq\lambda\leq\lambda_{0}$ determine a
certain non-empty convex closed subset $E\subset{\bf R}^{17}$. We have to
prove that the minimum of the function $G(T)=\lambda$, $T\in E$, is attained
on the constraint set $E$.

First, let us show this provided $F:{\mathcal{M}}\to{\mathcal{K}}({\bf
R}^{2})$. In this case $F(x)$, $F(x^{\prime})$, $F(y)$ and $F(y^{\prime})$ are
compact subsets of ${\bf R}^{2}$ so that the set $E$ is a compact subset of
${\bf R}^{17}$. Therefore, the continuous function $G$ takes the minimum value
on the set $E$ proving (6.22) in the case under consideration.

Let us prove (6.22) provided
$F:{\mathcal{M}}\to{\mathcal{H}}{\mathcal{P}}({\bf R}^{2})$. In this case the
sets $F(x)$, $F(x^{\prime})$, $F(y)$ are half-planes. We also recall that
$\|\cdot\|$ is the uniform norm in ${\bf R}^{2}$. These observation tell us
the set $E$ is determined by the finite number of linear constrains, i.e., $E$
is a non-empty convex polytope (not necessarily bounded) in ${\bf R}^{17}$.

We also note that the objective function $G(T)=\lambda$ is a linear functional
bounded from below on $E$ (because $\lambda\geq 0$). Thus, we have a problem
of linear programming on a non-empty convex polytope $E$ in ${\bf R}^{17}$
(i.e., with at least one feasible solution in the terminology of the linear
programming theory), and with the objective function is bounded from below on
the set $E$, the set of all feasible solutions. In this case, there exists an
optimal solution to this problem, see, e.g., [23], Theorem 4.2.3.

Thus, in the both cases, the infimum in the right hand side of (6.23) is
attained, and the proof of the lemma is complete. $\blacksquare$

Applying to $F$ the $\vec{\lambda}$-Projection Algorithm with an appropriate
parameter $\vec{\lambda}$, we obtain the following solution to Problem 1.2 for
the class ${\mathfrak{T}}$ of the set-valued mappings satisfying Condition
1.9.

###### Theorem 6.7

Let ${\mathfrak{M}}=({\mathcal{M}},\rho)$ be a pseudometric space, and let
$F:{\mathcal{M}}\to\operatorname{Conv}({\bf R}^{2})$ be a set-valued mapping.
Suppose that ${\mathfrak{M}}$ and $F$ satisfy Condition 1.9. Then the
following statements hold:

(i) There exists a Lipschitz selection of $F$ if and only if
$\Lambda_{{\mathcal{R}}}(F)<\infty$.

(ii) Suppose that $0<\Lambda_{{\mathcal{R}}}(F)<\infty$. Then for every
constant $\gamma>1$, the $\vec{\lambda}$-Projection Algorithm with

$\vec{\lambda}=(\,3\gamma\Lambda_{{\mathcal{R}}}(F),\,\gamma\Lambda_{{\mathcal{R}}}(F)\,)$

produces the outcome “Success” and returns the Lipschitz selection
$f_{\vec{\lambda};F}$ of $F$ with Lipschitz seminorm

$\|f_{\vec{\lambda};F}\|_{\operatorname{Lip}({\mathcal{M}})}\leq
5\gamma\,|F|_{{\mathfrak{M}}}.$

(iii) If $\Lambda_{{\mathcal{R}}}(F)=0$, then for every $\varepsilon>0$, the
$\vec{\lambda}$-Projection Algorithm with
$\vec{\lambda}=(3\varepsilon,\varepsilon)$ produces the outcome “Success” and
returns the Lipschitz selection $f_{\vec{\lambda};F}$ of $F$ with
$\|f_{\vec{\lambda};F}\|_{\operatorname{Lip}({\mathcal{M}})}\leq
5\varepsilon$.

(iv) Suppose that either $F:{\mathcal{M}}\to{\mathcal{K}}({\bf R}^{2})$ or
$F:{\mathcal{M}}\to{\mathcal{H}}{\mathcal{P}}({\bf R}^{2})$. If
$\Lambda_{{\mathcal{R}}}(F)$ is finite then for every $\gamma\geq 1$, the
$\vec{\lambda}$-PA with
$\vec{\lambda}=(\,3\gamma\Lambda_{{\mathcal{R}}}(F),\,\gamma\Lambda_{{\mathcal{R}}}(F)\,)$
produces the outcome “Success” and returns the Lipschitz selection
$f_{\vec{\lambda};F}$ of $F$ with Lipschitz seminorm
$\|f_{\vec{\lambda};F}\|_{\operatorname{Lip}({\mathcal{M}})}\leq
5\gamma\,|F|_{{\mathfrak{M}}}$.

Proof. Part (i) of the theorem is immediate from Theorem 1.10.

Let us prove parts (ii) and (iii). We set
$\hat{\lambda}=\gamma\Lambda_{{\mathcal{R}}}(F)$ if
$\Lambda_{{\mathcal{R}}}(F)\in(0,\infty)$, and $\hat{\lambda}=\varepsilon$ if
$\Lambda_{{\mathcal{R}}}(F)=0$. Because $\gamma>1$ and $\varepsilon>0$, we
have $\Lambda_{{\mathcal{R}}}(F)<\hat{\lambda}<\infty$. Therefore, thanks to
Definition 6.5, condition (1.18) of Theorem 1.10 is satisfied with
$\lambda=\hat{\lambda}$. Thus

$\displaystyle{\mathcal{R}}_{F}[x,x^{\prime}:\hat{\lambda}]\cap\\{{\mathcal{R}}_{F}[y,y^{\prime}:\hat{\lambda}]+\hat{\lambda}\,\rho(x,y)\,Q_{0}\\}\neq\emptyset~{}~{}~{}~{}~{}\text{for
every}~{}~{}x,x^{\prime},y,y^{\prime}\in{\mathcal{M}}$ (6.26)

proving that $F$ satisfies the hypothesis of Proposition 5.1 with
$\tilde{\lambda}=\lambda=\hat{\lambda}$. Thanks to this proposition, for every
$x,x^{\prime},x^{\prime\prime},y,y^{\prime},y^{\prime\prime}\in{\mathcal{M}}$,
we have:

${\mathcal{W}}_{F}[x,x^{\prime},x^{\prime\prime}:3\tilde{\lambda}]\cap\left\\{{\mathcal{W}}_{F}[y,y^{\prime},y^{\prime\prime}:3\tilde{\lambda}]+\lambda\,\rho(x,y)Q_{0}\right\\}\neq\emptyset.$

This property tells us that $F$ satisfies the hypothesis of Theorem 3.2 with

$\displaystyle\tilde{\lambda}=3\hat{\lambda}~{}~{}~{}\text{and}~{}~{}~{}\lambda=\hat{\lambda}.$
(6.27)

Now, let us apply to $F$ the
$\vec{\lambda}=(\lambda_{1},\lambda_{2})$-Projection Algorithm with
$\lambda_{1}=3\hat{\lambda}$ and $\lambda_{2}=\hat{\lambda}$, and prove that
this algorithm produces the outcome “Success”. In fact, we know that $F$
satisfies the hypothesis of Theorem 3.2. Lemma 3.3 tells us that in this case
the set $F^{[1]}[x:\tilde{\lambda}]\neq\emptyset$ for every
$x\in{\mathcal{M}}$. Furthermore, thanks to (3.16), the rectangle
${\mathcal{T}}_{F,\tilde{\lambda}}^{[1]}[x:\lambda]\neq\emptyset$ on
${\mathcal{M}}$. Thus, condition (6.8) holds proving that $\vec{\lambda}$-PA
produces the outcome “Success”. See Remark 6.2.

Parts ($\bigstar A$) and ($\bigstar B$) of Theorem 6.3 tell us that in this
case, the $\vec{\lambda}$-Projection Algorithm returns the mapping
$f_{\vec{\lambda};F}:{\mathcal{M}}\to{\bf R}^{2}$ which is a Lipschitz
selection of $F$ with the Lipschitz seminorm

$\displaystyle\|f_{\lambda;F}\|_{\operatorname{Lip}({\mathcal{M}})}\leq\lambda_{1}+2\lambda_{2}=3\hat{\lambda}+2\hat{\lambda}=5\hat{\lambda}.$
(6.28)

If $\Lambda_{{\mathcal{R}}}(F)=0$, then $\hat{\lambda}=\varepsilon$ so that
$\|f_{\lambda;F}\|_{\operatorname{Lip}({\mathcal{M}})}\leq 5\varepsilon$
proving part (iii) of the theorem. If $\Lambda_{{\mathcal{R}}}(F)>0$, then
$\|f_{\lambda;F}\|_{\operatorname{Lip}({\mathcal{M}})}\leq
5\gamma\Lambda_{{\mathcal{R}}}(F)$. From this inequality and (6.19), we have
$\|f_{\lambda;F}\|_{\operatorname{Lip}({\mathcal{M}})}\leq
5\gamma\,|F|_{{\mathfrak{M}}}$, and the proof of part (ii) of the theorem is
complete.

Let us prove part (iv) of the theorem. Thanks to Lemma 6.6, for arbitrary
$\gamma\geq 1$, condition (6.26) holds with
$\hat{\lambda}=\gamma\Lambda_{{\mathcal{R}}}(F)$. In other words, the set-
valued mapping $F$ satisfies the hypothesis of Proposition 5.1 with
$\tilde{\lambda}=\lambda=\hat{\lambda}$. This enables us to repeat the proof
of part (ii) of the theorem given above (for this choice of the constant
$\hat{\lambda}$). This proof leads us to the statement of part (iv) completing
the proof of the theorem. $\blacksquare$

Theorem 6.7 leads us to a solution to Problem 1.2 for pseudometric spaces
${\mathfrak{M}}$ and set-valued mappings $F$ satisfying Condition 1.9. For
simplicity, let us demonstrate this solution for the case of a finite set
${\mathcal{M}}$ and a set-valued mapping $F:{\mathcal{M}}\to{\mathfrak{T}}$
where ${\mathfrak{T}}$ is either the family ${\mathcal{K}}({\bf R}^{2})$ or
the family ${\mathcal{H}}{\mathcal{P}}({\bf R}^{2})$. (See (1.3) and (1.4).)

###### Algorithm 6.8

(A constructive algorithm for a nearly optimal Lipschitz selection.) Given a
finite pseudometric space ${\mathfrak{M}}=({\mathcal{M}},\rho)$, and a set-
valued mapping $F:{\mathcal{M}}\to{\mathfrak{T}}$, the algorithm produces a
nearly optimal Lipschitz selection $f$ of $F$ (the outcome “Success”) or stops
(the outcome “No go”). This procedure includes the following two main steps.

STEP 1. At this step we compute the constant $\Lambda_{{\mathcal{R}}}(F)$. If
it turns out that $\Lambda_{{\mathcal{R}}}(F)=+\infty$, then a Lipschitz
selection of $F$ does not exist. In this case, the algorithm produces the
outcome “No go” and stops.

If we determine that $\Lambda_{{\mathcal{R}}}(F)<+\infty$, we calculate this
constant up to some constant $\gamma\geq 1$. Thus, at this step the algorithm
returns the number $\gamma\,\Lambda_{{\mathcal{R}}}(F)$.

STEP 2. At this step we apply to $F$ the
$\vec{\lambda}=(\lambda_{1},\lambda_{2})$-Projection Algorithm with

$\displaystyle\lambda_{1}=3\gamma\,\Lambda_{{\mathcal{R}}}(F)~{}~{}~{}~{}\text{and}~{}~{}~{}~{}\lambda_{2}=\gamma\,\Lambda_{{\mathcal{R}}}(F).$
(6.29)

The Projection Algorithm produces the outcome “Success” and returns the
mapping $f_{\vec{\lambda};F}$ which is a Lipschitz selection of $F$ with
Lipschitz seminorm

$\displaystyle\|f_{\lambda;F}\|_{\operatorname{Lip}({\mathcal{M}})}\leq
5\gamma\,\Lambda_{{\mathcal{R}}}(F).$ (6.30)

At this stage, Algorithm 6.8 produces the outcome “Success” and stops.
$\blacksquare$

Note that Algorithm 6.8 is immediate from part (iv) of Theorem 6.7.

###### Remark 6.9

(i) Clearly, if ${\mathfrak{M}}=({\mathcal{M}},\rho)$ is a metric space and
${\mathcal{M}}$ is finite then any selection $f$ of the set-valued mapping $F$
from Algorithm 6.8 is Lipschitz, i.e.,
$\|f\|_{\operatorname{Lip}({\mathcal{M}})}<\infty$. Hence,
$|F|_{{\mathfrak{M}}}<\infty$, so that, thanks to inequality (6.19),
$\Lambda_{{\mathcal{R}}}(F)<\infty$ as well. Thus, if $\rho$ is a metric and
${\mathcal{M}}$ is finite, Algorithm 6.8 always produces the outcome
“Success”.

However, if $\rho$ is a pseudometric, i.e., $\rho(x,y)=0$ may hold with
certain $x\neq y$, in general, the quantity $\Lambda_{{\mathcal{R}}}(F)$ may
take the value $+\infty$ (even for a finite set ${\mathcal{M}}$). For
instance, if there exist elements $x,x^{\prime}\in{\mathcal{M}}$ such that
$\rho(x,x^{\prime})=0$ and $F(x)\cap F(x^{\prime})=\emptyset$, then, thanks to
(1.17), ${\mathcal{R}}_{F}[x,x^{\prime}:\lambda]=\emptyset$ for every
$\lambda\geq 0$. Therefore, inequality (1.18) does not hold for every
$y,y^{\prime}\in{\mathcal{M}}$ and any $\lambda\geq 0$ proving that
$\Lambda_{{\mathcal{R}}}(F)=+\infty$. See Definition 6.5. It is also clear
that in this case $F$ does not have a Lipschitz selection (with respect to the
pseudometric $\rho$).

(ii) In general, the precise computation of the quantity
$\Lambda_{{\mathcal{R}}}(F)$ maybe a very difficult technical problem. For
this reason, we introduce in Algorithm 6.8 the parameter $\gamma\geq 1$ which
enables us to calculate $\Lambda_{{\mathcal{R}}}(F)$ up to this parameter.
Inequality (6.30) tells us that in this case the algorithm construct a
selection of $F$ whose Lipschitz seminorm is bounded by a constant linearly
depending on $\gamma$. $\blacktriangleleft$

6.3 The constant $\Lambda_{{\mathcal{R}}}(F)$ and other related constants.

In this section we give several remarks related to efficient algorithms for
computing the constant $\Lambda_{{\mathcal{R}}}(F)$. See Definition 6.5.

Theorem 5.6 motivates us to introduce the following constant.

###### Definition 6.10

Let ${\mathfrak{M}}=({\mathcal{M}},\rho)$ be a pseudometric space, and let
$F:{\mathcal{M}}\to\operatorname{Conv}({\bf R}^{2})$ be a set-valued mapping.
Let

$\displaystyle{\mathcal{L}}_{{\mathcal{R}}}^{(int)}(F)=\\{\lambda\geq
0:\bigcap_{y,y^{\prime}\in{\mathcal{M}}}\left\\{\,{\mathcal{R}}_{F}[y,y^{\prime}:\lambda]+\lambda\,\rho(x,y)Q_{0}\right\\}\neq\emptyset~{}\,\text{for
all}~{}x\in{\mathcal{M}}\\}.$ (6.31)

Let

$\displaystyle\Lambda_{{\mathcal{R}}}^{(int)}(F)=\inf{\mathcal{L}}_{{\mathcal{R}}}^{(int)}(F)$
(6.32)

provided ${\mathcal{L}}_{{\mathcal{R}}}^{(int)}(F)\neq\emptyset$, and let
$\Lambda_{{\mathcal{R}}}^{(int)}(F)=+\infty$ if
${\mathcal{L}}_{{\mathcal{R}}}^{(int)}(F)=\emptyset$. $\blacktriangleleft$

Thus, $\Lambda_{{\mathcal{R}}}^{(int)}(F)$ is the infimum of constants
$\lambda\geq 0$ such that condition (5.6) of Theorem 5.6 holds.

###### Lemma 6.11

Let ${\mathfrak{M}}=({\mathcal{M}},\rho)$ be a pseudometric space, and let
$F:{\mathcal{M}}\to\operatorname{Conv}({\bf R}^{2})$ be a set-valued mapping.
Suppose that either ${\mathcal{M}}$ is finite or at least one of the sets
$F(x)$, $x\in{\mathcal{M}}$, is compact.

Then
${\mathcal{L}}_{{\mathcal{R}}}^{(int)}(F)={\mathcal{L}}_{{\mathcal{R}}}(F)$
and $\Lambda_{{\mathcal{R}}}^{(int)}(F)=\Lambda_{{\mathcal{R}}}(F)$.

Proof. Clearly, thanks to (6.18) and (6.32), it suffices to prove the equality
${\mathcal{L}}_{{\mathcal{R}}}^{(int)}(F)={\mathcal{L}}_{{\mathcal{R}}}(F)$.

If $\lambda\in{\mathcal{L}}_{{\mathcal{R}}}^{(int)}(F)$, then, thanks to
(6.31), for every $x\in{\mathcal{M}}$, we have

$\displaystyle\bigcap_{y,y^{\prime}\in{\mathcal{M}}}\left\\{\,{\mathcal{R}}_{F}[y,y^{\prime}:\lambda]+\lambda\,\rho(x,y)Q_{0}\right\\}\neq\emptyset.$
(6.33)

Clearly, thanks to this property, for every
$x,x^{\prime},y,y^{\prime}\in{\mathcal{M}}$, we have

$\displaystyle{\mathcal{R}}_{F}[x,x^{\prime}:\lambda]\cap\\{{\mathcal{R}}_{F}[y,y^{\prime}:\lambda]+\lambda\,\rho(x,y)\,Q_{0}\\}\neq\emptyset$
(6.34)

proving that $\lambda\in{\mathcal{L}}_{{\mathcal{R}}}(F)$, see (6.17).

Conversely, suppose that $\lambda\in{\mathcal{L}}_{{\mathcal{R}}}(F)$, i.e.,
(6.34) holds for all $x,x^{\prime},y,y^{\prime}\in{\mathcal{M}}$. Prove that
in this case, for every $x\in{\mathcal{M}}$, property (6.33) holds as well.

We set

${\mathcal{V}}=\\{{\mathcal{R}}_{F}[y,y^{\prime}:\lambda]+\lambda\,\rho(x,y)Q_{0}:y,y^{\prime}\in{\mathcal{M}}\\}.$

Let us prove that any two members of the family ${\mathcal{V}}$ have a common
point. Indeed, thanks to (6.34), given
$y,y^{\prime},z,z^{\prime}\in{\mathcal{M}}$, there exist points
$a\in{\mathcal{R}}_{F}[y,y^{\prime}:\lambda]$ and
$b\in{\mathcal{R}}_{F}[z,z^{\prime}:\lambda]$ such that
$\|a-b\|\leq\lambda\,\rho(y,z)$. Therefore, thanks to the triangle inequality,
$\|a-b\|\leq\lambda\,(\rho(y,x)+\rho(x,z))$ so that there exists a point
$w\in[a,b]$ such that $\|a-w\|\leq\lambda\,\rho(y,x)$ and
$\|b-w\|\leq\lambda\,\rho(z,x)$. Hence,

$w\in\\{{\mathcal{R}}_{F}[y,y^{\prime}:\lambda]+\lambda\,\rho(x,y)Q_{0}\\}\cap\\{{\mathcal{R}}_{F}[z,z^{\prime}:\lambda]+\lambda\,\rho(x,z)Q_{0}\\}$

proving the required property of the family ${\mathcal{V}}$.

From this property and the lemma’s hypothesis, it follows that the family
${\mathcal{V}}$ satisfies the hypothesis of Lemma 2.2 (i.e., Helly’s theorem
for rectangles). Thanks to this lemma, the family ${\mathcal{V}}$ has non-
empty intersection proving the required property (6.33).

The proof of the lemma is complete. $\blacksquare$

Below we will see how the equality
$\Lambda_{{\mathcal{R}}}^{(int)}(F)=\Lambda_{{\mathcal{R}}}(F)$, i.e., the
representation of $\Lambda_{{\mathcal{R}}}(F)$ in the form
$\Lambda_{{\mathcal{R}}}(F)=\inf{\mathcal{L}}_{{\mathcal{R}}}^{(int)}(F)$, see
(6.32), will help us calculate this constant in an efficient way.

But now we introduce one more useful constant directly related to the
Finiteness Principle in ${\bf R}^{2}$, see Theorem 5.2.

###### Definition 6.12

Let ${\mathfrak{M}}=({\mathcal{M}},\rho)$ be a pseudometric space, and let
$F:{\mathcal{M}}\to\operatorname{Conv}({\bf R}^{2})$ be a set-valued mapping.
We let ${\mathcal{L}}^{({\mathcal{F}}{\mathcal{P}})}(F)$ denote the family of
all constants $\lambda\geq 0$ such that for every subset
${\mathcal{M}}^{\prime}\subset{\mathcal{M}}$ consisting of at most four
points, the restriction $F|_{{\mathcal{M}}^{\prime}}$ of $F$ to
${\mathcal{M}}^{\prime}$ has a Lipschitz selection
$f_{{\mathcal{M}}^{\prime}}$ with Lipschitz seminorm
$\|f_{{\mathcal{M}}^{\prime}}\|_{\operatorname{Lip}({\mathcal{M}}^{\prime})}\leq\lambda$.

Let

$\displaystyle\Lambda^{({\mathcal{F}}{\mathcal{P}})}(F)=\inf{\mathcal{L}}^{({\mathcal{F}}{\mathcal{P}})}(F)$
(6.35)

provided ${\mathcal{L}}^{({\mathcal{F}}{\mathcal{P}})}(F)\neq\emptyset$, and
let $\Lambda^{({\mathcal{F}}{\mathcal{P}})}(F)=+\infty$ if
${\mathcal{L}}^{({\mathcal{F}}{\mathcal{P}})}(F)=\emptyset$.
$\blacktriangleleft$

Thus, $\Lambda^{({\mathcal{F}}{\mathcal{P}})}(F)$ is the smallest $\lambda\geq
0$ such that the hypothesis of Theorem 5.2 holds. Clearly,

$\displaystyle\Lambda^{({\mathcal{F}}{\mathcal{P}})}(F)=\sup\,\\{|F|_{{\mathcal{M}}^{\prime}}|_{{\mathfrak{M}}}:M^{\prime}\subset
M,\,\\#M^{\prime}\leq 4\\}.\hskip 42.67912pt\text{See (\ref{FM}).}$ (6.36)

Furthermore, thanks to Definitions 6.5 and 6.12 and formula (6.36), the
following inequality

$\displaystyle\Lambda_{{\mathcal{R}}}(F)\leq\Lambda^{({\mathcal{F}}{\mathcal{P}})}(F)\leq|F|_{{\mathfrak{M}}}$
(6.37)

holds provided $F:{\mathcal{M}}\to\operatorname{Conv}({\bf R}^{2})$ is an
arbitrary set-valued mapping. Moreover, if ${\mathcal{M}}$ and $F$ satisfy
Condition 1.9, then, thanks to Theorem 1.10 and Theorem 5.2, we have

$\displaystyle|F|_{{\mathfrak{M}}}\leq\min\,\left\\{5\Lambda_{{\mathcal{R}}}(F),3\Lambda^{({\mathcal{F}}{\mathcal{P}})}(F)\right\\}.$
(6.38)

###### Lemma 6.13

Let ${\mathfrak{M}}=({\mathcal{M}},\rho)$ be a pseudometric space, and let
$F:{\mathcal{M}}\to{\mathfrak{T}}$ where ${\mathfrak{T}}$ is either
${\mathcal{K}}({\bf R}^{2})$ or ${\mathcal{H}}{\mathcal{P}}({\bf R}^{2})$. If
$\Lambda_{{\mathcal{R}}}(F)<\infty$, then
$\Lambda^{({\mathcal{F}}{\mathcal{P}})}(F)\in{\mathcal{L}}^{({\mathcal{F}}{\mathcal{P}})}(F)$.
Cf. (6.35).

Proof. We follow the scheme of the proof of Lemma 6.6, and use equality
(6.36). We leave the details to the interested reader. $\blacksquare$

###### Theorem 6.14

Let ${\mathfrak{M}}=({\mathcal{M}},\rho)$ be a pseudometric space, and let
$F:{\mathcal{M}}\to\operatorname{Conv}({\bf R}^{2})$ be a set-valued mapping.
Suppose that either $F:{\mathcal{M}}\to{\mathcal{K}}({\bf R}^{2})$ or
$F:{\mathcal{M}}\to{\mathcal{H}}{\mathcal{P}}({\bf R}^{2})$.

If $\Lambda^{({\mathcal{F}}{\mathcal{P}})}(F)<\infty$, then for every
$\gamma\geq 1$, the $\vec{\lambda}$-Projection Algorithm with

$\vec{\lambda}=(\,\gamma\Lambda^{({\mathcal{F}}{\mathcal{P}})}(F),\,\gamma\Lambda^{({\mathcal{F}}{\mathcal{P}})}(F)\,)$

produces the outcome “Success” and returns the Lipschitz selection
$f_{\vec{\lambda};F}$ of $F$ with Lipschitz seminorm
$\|f_{\vec{\lambda};F}\|_{\operatorname{Lip}({\mathcal{M}})}\leq
3\gamma\,|F|_{{\mathfrak{M}}}$.

Proof. We follow the approach suggested in the proof of part (iv) of Theorem
6.7. Thanks to Lemma 6.13,
$\gamma\Lambda^{({\mathcal{F}}{\mathcal{P}})}(F)\in{\mathcal{L}}^{({\mathcal{F}}{\mathcal{P}})}(F)$
for every $\gamma\geq 1$. In other words, for every subset
${\mathcal{M}}^{\prime}\subset{\mathcal{M}}$ consisting of at most four
points, the restriction $F|_{{\mathcal{M}}^{\prime}}$ of $F$ to
${\mathcal{M}}^{\prime}$ has a Lipschitz selection
$f_{{\mathcal{M}}^{\prime}}$ with Lipschitz seminorm
$\|f_{{\mathcal{M}}^{\prime}}\|_{\operatorname{Lip}({\mathcal{M}}^{\prime})}\leq\lambda$
where $\lambda=\gamma\Lambda^{({\mathcal{F}}{\mathcal{P}})}(F)$. As we have
shown in the sufficiency part of the proof of Theorem 5.2, in this case
condition (3.3) of Theorem 3.2 is satisfied with $\tilde{\lambda}=\lambda$.
Combining this condition with the hypothesis of Theorem 6.14, we conclude that
${\mathfrak{M}}$ and $F$ satisfy the hypothesis of Theorem 3.2 with
$\tilde{\lambda}=\lambda=\gamma\Lambda^{({\mathcal{F}}{\mathcal{P}})}(F)$ and
$\lambda=\gamma\Lambda^{({\mathcal{F}}{\mathcal{P}})}(F)$.

We then repeat the proof of part (ii) of Theorem 6.7 from definition (6.27) up
to and including inequality (6.28), setting $\tilde{\lambda}=\lambda$ and
$\lambda_{1}=\lambda_{2}=\lambda$ in this proof. As a result, we show that in
this case the $\vec{\lambda}$-Projection Algorithm with
$\vec{\lambda}=(\lambda,\lambda)$ produces the outcome “Success” and returns
the mapping $f_{\vec{\lambda};F}:{\mathcal{M}}\to{\bf R}^{2}$ which is a
Lipschitz selection of $F$ with the Lipschitz seminorm

$\|f_{\lambda;F}\|_{\operatorname{Lip}({\mathcal{M}})}\leq\lambda_{1}+2\lambda_{2}=3\lambda=3\gamma\Lambda^{({\mathcal{F}}{\mathcal{P}})}(F).$

But $\Lambda^{({\mathcal{F}}{\mathcal{P}})}(F)\leq|F|_{{\mathfrak{M}}}$, see
(6.37), and the proof of the theorem is complete. $\blacksquare$

###### Algorithm 6.15

Theorem 6.14 leads us to a new algorithm for a nearly optimal Lipschitz
selection of a set-valued mapping. We obtain this algorithm by a slight
modification of Algorithm 6.8. More specifically, at STEP 1 of this algorithm
we replace the parameter $\Lambda_{{\mathcal{R}}}(F)$ with the parameter
$\Lambda^{({\mathcal{F}}{\mathcal{P}})}(F)$. At STEP 2 of Algorithm 6.8 we set

$\displaystyle\lambda_{1}=\gamma\,\Lambda^{({\mathcal{F}}{\mathcal{P}})}(F)~{}~{}~{}~{}\text{and}~{}~{}~{}~{}\lambda_{2}=\gamma\,\Lambda^{({\mathcal{F}}{\mathcal{P}})}(F).$
(6.39)

Then, thanks to Theorem 6.14, inequality (6.30) transforms into the following
one:

$\|f_{\lambda;F}\|_{\operatorname{Lip}({\mathcal{M}})}\leq
3\gamma\,\Lambda_{{\mathcal{R}}}(F).$

At this stage, Algorithm 6.15 produces the outcome “Success” and stops.
$\blacksquare$

Let us make two remarks related to some preliminary estimates of the
computational efficiency of Algorithm 6.8 and Algorithm 6.15.

###### Remark 6.16

We note that at the second step of Algorithms 6.8 and 6.15 the
$\vec{\lambda}$-Projection Algorithm is applied with some parameters
$\vec{\lambda}=(\lambda_{1},\lambda_{2})$, see (6.29) and (6.39). In the
forthcoming paper [35] we will show that if ${\mathcal{M}}$ is an $N$-element
pseudometric space and $F$ satisfies certain rather mild geometric conditions,
the running time of the $\vec{\lambda}$-Projection Algorithm is $O(N^{3})$. In
particular, this is true provided each $F(x)$ is a half-plane, i.e.,
$F:{\mathcal{M}}\to{\mathcal{H}}{\mathcal{P}}({\bf R}^{2})$.

The most difficult part of Algorithms 6.8 and 6.15 is STEP 1, i.e.,
calculation (up to some constant $\gamma\geq 1$) the values of the constants
$\Lambda_{{\mathcal{R}}}(F)$ and $\Lambda^{({\mathcal{F}}{\mathcal{P}})}(F)$
respectively. Although the definitions of these constants are given in
explicit geometric terms, their calculation may require a huge number of
computer operations. (Even if every set $F(x)$, $x\in{\mathcal{M}}$, is a disc
in ${\bf R}^{2}$, it is not clear how to calculate
$\Lambda_{{\mathcal{R}}}(F)$ and $\Lambda^{({\mathcal{F}}{\mathcal{P}})}(F)$
(even up to an absolute constant)).

Let us consider the simplest non-trivial case of a set-valued mapping from
${\mathcal{M}}$ (with $\\#{\mathcal{M}}=N$) to the family
${\mathcal{H}}{\mathcal{P}}({\bf R}^{2})$ of all half-planes in ${\bf R}^{2}$.

It is not difficult to compute $\Lambda_{{\mathcal{R}}}(F)$ with $O(N^{4})$
running time. Indeed, to calculate the constant $\Lambda_{{\mathcal{R}}}(F)$
we have to consider all possible (ordered) quadruples
$T=(x,x^{\prime},y,y^{\prime})\subset{\mathcal{M}}$ and solve the
corresponding linear programming problem determined by (6.23), (6.24) and
(6.25). For each $T$, solving this problem will take $O(1)$ running time.
Since the number of such quadruples $T$ is $O(N^{4})$, the total running time
is also $O(N^{4})$. The same estimate $O(N^{4})$ is obtained for the running
time of computing the constant $\Lambda^{({\mathcal{F}}{\mathcal{P}})}(F)$.

Thus, for both Algorithm 6.8 and Algorithm 6.15 this approach provides the
running time

$O(N^{4})\,~{}\text{(at {\bf STEP 1})}+O(N^{3})\,~{}\text{(at {\bf STEP
2})}=O(N^{4}).\text{\hskip 28.45274pt$\blacktriangleleft$}$

###### Remark 6.17

For the same case of a set-valued mapping
$F:{\mathcal{M}}\to{\mathcal{H}}{\mathcal{P}}({\bf R}^{2})$ defined on a
finite set ${\mathcal{M}}$ with $\\#{\mathcal{M}}=N$, there exists another
algorithm for calculating the constant $\Lambda_{{\mathcal{R}}}(F)$ with
$O(N^{3})$ running time. Let us briefly explain the main idea of this
algorithm.

Definition 6.10 and Lemma 6.11 tell us that, in the case under the
consideration,
$\Lambda_{{\mathcal{R}}}^{(int)}(F)=\Lambda_{{\mathcal{R}}}(F)$. Thus,
$\Lambda_{{\mathcal{R}}}^{(int)}(F)=\inf\lambda$ where $\lambda$ runs over all
non-negative numbers such that for every $x\in{\mathcal{M}}$ there exists a
point $u\in{\bf R}^{2}$ such that

$\displaystyle
u\in{\mathcal{R}}_{F}[y,y^{\prime}:\lambda]+\lambda\,\rho(x,y)Q_{0}$ (6.40)

for all $y,y^{\prime}\in{\mathcal{M}}$.

Fix $x\in{\mathcal{M}}$ and consider the family ${\mathcal{V}}_{x}$ of all
points $v=(u,\lambda)\in{\bf R}^{3}$ with $\lambda\geq 0$ such that property
(6.40) holds. The reader can easily see that ${\mathcal{V}}_{x}$ is
intersection of at most four half-spaces in ${\bf R}^{3}$. Each of these half-
spaces depends only on parameters determined the half-planes $F(y)$ and
$F(y^{\prime})$. Hence, the total number of linear constraints determining the
set ${\mathcal{V}}_{x}\subset{\bf R}^{3}$ is bounded by $O(N^{2})$.

Let
$\Lambda_{{\mathcal{R}},x}(F)=\\{\inf\lambda:(u,\lambda)\in{\mathcal{V}}_{x}\\}$.
Then,

$\displaystyle\Lambda_{{\mathcal{R}}}(F)=\max_{x\in{\mathcal{M}}}\Lambda_{{\mathcal{R}},x}(F).$
(6.41)

Let us see that there exists an algorithm which for every $x\in{\mathcal{M}}$,
computes the quantity $\Lambda_{{\mathcal{R}},x}(F)$ with the running time
$O(N^{2})$. Indeed, we know that the problem

$\displaystyle\text{\it Find}~{}~{}~{}\inf\lambda~{}~{}~{}\text{\it under the
condition}~{}~{}~{}(u,\lambda)\in{\mathcal{V}}_{x},$ (6.42)

is a linear program in three variables with $O(N^{2})$ linear constraints. The
following theorem is the classical results on low-dimensional linear
programming by N. Megiddo [24] and M. E. Dyer [9].

###### Theorem 6.18

A linear program in three variables and $m$ constraints can be solved in
$O(m)$ time.

This theorem implies the following useful corollary.

###### Corollary 6.19

(i) There exists an algorithm which given a convex polygon $G\subset{\bf
R}^{2}$ determined by $N$ linear constraints, constructs its rectangular hull
${\mathcal{H}}[G]$ in $O(N)$ running time.

(ii) There exists an algorithm which given a point $A\in{\bf R}^{2}$ and a
convex polygon $G\subset{\bf R}^{2}$ determined by $N$ linear constraints,
calculates the distance from $A$ to $G$ using at most $O(N)$ computer
operations.

Proof. These results are well known in the theory of geometric algorithms.
Each of them can be readily reduced to a certain linear program in three
variables and $CN$ constraints where $C$ is an absolute constant. Applying
Theorem 6.18 to the corresponding linear program, we obtain the statements of
the corollary. We leave the details to the interested reader. $\blacksquare$

Thus, for every $x\in{\mathcal{M}}$ the problem (6.42) can be solved in
$O(N^{2})$ time so that, thanks to (6.41), the constant
$\Lambda_{{\mathcal{R}}}(F)$ can be calculated in $N\cdot O(N^{2})=O(N^{3})$
time.

Combining this algorithm for $\Lambda_{{\mathcal{R}}}(F)$ with Algorithm 6.8,
we obtain a constructive algorithm which, given a set-valued mapping
$F:{\mathcal{M}}\to{\mathcal{H}}{\mathcal{P}}({\bf R}^{2})$ assigns a
Lipschitz selection $f$ of $F$ with
$\|f\|_{\operatorname{Lip}({\mathcal{M}})}\leq 5\,|F|_{{\mathfrak{M}}}$. The
running time of this algorithm is

$O(N^{3})\,~{}\text{({\bf STEP 1})}+O(N^{3})\,~{}\text{({\bf STEP
2})}=O(N^{3}).~{}~{}~{}~{}~{}~{}\text{\hskip 28.45274pt$\blacktriangleleft$}$

6.4 Lipschitz selections of polygon-set valued mappings.

In this section, we provide some remarks related to a recent paper by C.
Fefferman and B. Pegueroles [16]. Let $D$ and $L$ be positive integers and let
${\mathscr{P}}_{L}({\bf R}^{D})$ be the family of all compact convex polytope
in ${\bf R}^{D}$ defined by at most $L$ linear constraints. In [16] C.
Fefferman and B. Pegueroles solved a selection problem for set-valued mappings
$F$ from a set $E\subset{\bf R}^{n}$ into ${\mathscr{P}}_{L}({\bf R}^{D})$
with a slight enlarging of the targets $F(x)$, $x\in E$. (See also [12,
Chapter 7.2].) Let us recall a particular case of this result related to
Lipschitz selections. Let $E$ be a finite subset of ${\bf R}^{n}$ with
$\\#E=N$, and let $F:E\to{\mathscr{P}}_{L}({\bf R}^{D})$ be a set-valued
mapping. Given $\tau>0$ and $x\in E$, we let $(1+\tau)\lozenge F(x)$ denote
the convex set obtained by dilating $F(x)$ about its center of mass by a
factor $(1+\tau)$.

###### Theorem 6.20

Let $M,\tau>0$ be given. The algorithm described in [16] produces one of the
following two outcomes, using at most $C_{1}\,N\log N$ computer operations and
$C_{1}\,N$ units of computer memory.

Outcome 1 (“No Go”): We guarantee that there does not exist
$f\in\operatorname{Lip}(E,{\bf R}^{D})$ with the Lipschitz seminorm $\leq M$
such that $f(x)\in F(x)$ for all $x\in E$.

Outcome 2 (“Success”): The algorithm produces a mapping $f:E\to{\bf R}^{D}$
with the Lipschitz seminorm at most $C_{2}\,M$ satisfying
$f(x)\in(1+\tau)\lozenge F(x)$ for all $x\in E$.

Here, $C_{1}>0$ depends only on $\tau$, $L$, $n$ and $D$, and $C_{2}>0$
depends only on $n$ and $D$.

This theorem motivates us to consider Problem 1.2 for the family
${\mathfrak{T}}={\mathscr{P}}_{L}({\bf R}^{2})$ of all non-empty convex
polygons in ${\bf R}^{2}$ each defined by at most $L$ linear constraints. Let
us note that this problem is a particular case of the same problem but for the
family ${\mathfrak{T}}={\mathcal{H}}{\mathcal{P}}({\bf R}^{2})$ of all half-
planes in ${\bf R}^{2}$. Indeed, let ${\mathfrak{M}}=({\mathcal{M}},\rho)$ be
a pseudometric space, and let $F:{\mathcal{M}}\to{\mathscr{P}}_{L}({\bf
R}^{2})$ be a set-valued mapping. We know that each polygon $F(x)$,
$x\in{\mathcal{M}}$, can be represented as an intersection of at most $L$
half-planes. We denote this family of half-planes by ${\mathscr{H}}_{F}(x)$;
thus

$\displaystyle F(x)=\cap\\{H:H\in{\mathscr{H}}_{F}(x)\\}~{}~{}~{}\text{for
every}~{}~{}~{}x\in{\mathcal{M}}.$ (6.43)

We introduce a new pseudometric space
$\widetilde{\mathfrak{M}}=(\widetilde{{\mathcal{M}}},\tilde{\rho})$ whose
elements are all couples $u=(x,H)$ where $x\in{\mathcal{M}}$ and
$H\in{\mathscr{H}}_{F}(x)$. We define on $\widetilde{{\mathcal{M}}}$ The
pseudometric $\tilde{\rho}$ on $\widetilde{{\mathcal{M}}}$ is defined by

$\tilde{\rho}(u,u^{\prime})=\rho(x,x^{\prime})~{}~{}~{}\text{for
every}~{}~{}~{}u=(x,H),~{}u^{\prime}=(x^{\prime},H^{\prime})\in\widetilde{{\mathcal{M}}}.$

Finally, we define a new set-valued mapping
$\widetilde{F}:\widetilde{{\mathcal{M}}}\to{\mathcal{H}}{\mathcal{P}}({\bf
R}^{2})$ by letting

$\displaystyle\widetilde{F}((x,H))=H~{}~{}~{}\text{provided}~{}~{}~{}x\in{\mathcal{M}}~{}~{}\text{and}~{}~{}H\in{\mathscr{H}}_{F}(x).$
(6.44)

In particular, $\tilde{\rho}((x,H),(x,H^{\prime}))=0$ for every
$H,H^{\prime}\in{\mathscr{H}}_{F}(x)$. This observation implies the following
simple claim.

###### Claim 6.21

(i) If a mapping $f:{\mathcal{M}}\to{\bf R}^{2}$ is a Lipschitz selection of
$F$ then the mapping $\tilde{f}:\widetilde{{\mathcal{M}}}\to{\bf R}^{2}$
defined by

$\displaystyle\tilde{f}((x,H))=f(x),~{}~{}~{}~{}(x,H)\in\widetilde{{\mathcal{M}}},$
(6.45)

is a Lipschitz (with respect to $\tilde{\rho}$) selection of $\widetilde{F}$,
and the following equality

$\displaystyle\|\tilde{f}\|_{\operatorname{Lip}(\widetilde{{\mathcal{M}}},\tilde{\rho})}=\|f\|_{\operatorname{Lip}({\mathcal{M}},\rho)}$
(6.46)

holds.

(ii) Conversely, if a mapping $\tilde{f}:\widetilde{{\mathcal{M}}}\to{\bf
R}^{2}$ is a Lipschitz (with respect to $\tilde{\rho}$) selection of
$\widetilde{F}$, then there exists a unique mapping $f:{\mathcal{M}}\to{\bf
R}^{2}$ satisfying (6.45). Furthermore, $f$ is a Lipschitz selection of $F$,
and equality (6.46) holds.

Proof. Part (i) of the claim is obvious. Let us prove part (ii). Because
$\tilde{f}$ is Lipschitz (with respect to $\tilde{\rho}$), for every
$x\in{\mathcal{M}}$ and every $H,H^{\prime}\in{\mathscr{H}}_{F}(x)$, we have

$\displaystyle\|\tilde{f}((x,H))-\tilde{f}((x,H^{\prime}))\|\leq\|\tilde{f}\|_{\operatorname{Lip}(\widetilde{{\mathcal{M}}},\tilde{\rho})}\,\rho(x,x)=0.$
(6.47)

This enables us to define a mapping $f:{\mathcal{M}}\to{\bf R}^{2}$ by letting

$\displaystyle
f(x)=\tilde{f}((x,H))~{}~{}\text{where}~{}~{}H\in{\mathscr{H}}_{F}(x)~{}~{}\text{is
arbitrary}.$ (6.48)

Thanks to (6.47), $f$ is well defined (i.e., $\tilde{f}((x,H))$ depends only
on $x$ and independent of $H$ provided $H\in{\mathscr{H}}_{F}(x)$).
Furthermore, $f$ is a selection of $F$ on ${\mathcal{M}}$. Indeed, because
$\tilde{f}$ which is a Lipschitz selection of $\widetilde{F}$, the point
$\tilde{f}((x,H))\in\widetilde{F}((x,H))$ for every
$H\in{\mathscr{H}}_{F}(x)$. Hence, thanks to (6.48),
$f(x)\in\widetilde{F}((x,H))$ for all $H\in{\mathscr{H}}_{F}(x)$ proving that

$f(x)\in\cap\\{H:H\in{\mathscr{H}}_{F}(x)\\}=F(x).~{}~{}~{}~{}\text{See
(\ref{FH-CR}).}$

Finally, thanks to (6.48) and part (i) of the claim, the equality (6.46)holds.
$\blacksquare$

Applying the Projection Algorithm 6.1 to the pseudometric space
$\widetilde{\mathfrak{M}}=(\widetilde{{\mathcal{M}}},\tilde{\rho})$ and the
set-valued mapping
$\widetilde{F}:\widetilde{{\mathcal{M}}}\to{\mathcal{H}}{\mathcal{P}}({\bf
R}^{2})$, we obtain the following theorem.

###### Theorem 6.22

Let a positive integer $L$ and a constant $M>0$ be given. Let
${\mathfrak{M}}=({\mathcal{M}},\rho)$ be a finite pseudometric space with
$\\#{\mathcal{M}}=N$, and let $F:{\mathcal{M}}\to{\mathscr{P}}_{L}({\bf
R}^{2})$ be a set-valued mapping.

The $(M,M)$-Projection Algorithm produces one of the following two outcomes,
using $O(L^{3}N^{3})$ computer operations.

Outcome 1 (“No Go”): We guarantee that there does not exist
$f\in\operatorname{Lip}({\mathcal{M}})$ with the Lipschitz seminorm
$\|f\|_{\operatorname{Lip}({\mathcal{M}})}\leq M$ such that $f(x)\in F(x)$ for
all $x\in{\mathcal{M}}$.

Outcome 2 (“Success”): The algorithm produces a mapping
$f:{\mathcal{M}}\to{\bf R}^{2}$ with the Lipschitz seminorm
$\|f\|_{\operatorname{Lip}({\mathcal{M}})}\leq 3M$ satisfying $f(x)\in F(x)$
for all $x\in{\mathcal{M}}$.

Proof. We set $\vec{\lambda}=(\lambda_{1},\lambda_{2})$ where
$\lambda_{1}=\lambda_{2}=M$. Then we apply Theorem 6.3 with this
$\vec{\lambda}$ to
$\widetilde{\mathfrak{M}}=(\widetilde{{\mathcal{M}}},\tilde{\rho})$ and
$\widetilde{F}:\widetilde{{\mathcal{M}}}\to{\mathcal{H}}{\mathcal{P}}({\bf
R}^{2})$. This theorem tells us that the $\vec{\lambda}$-Projection Algorithm
produces the following two outcomes:

Outcome 1 “No go”. In this case we guarantee that there does not exist a
Lipschitz selection of $\widetilde{F}$ with Lipschitz seminorm at most
$\min\\{\lambda_{1},\lambda_{2}\\}=M$;

Outcome 2 “Success”. In this case, the $\vec{\lambda}$-PA returns a mapping
$\tilde{f}:\widetilde{{\mathcal{M}}}\to{\bf R}^{2}$ which is a Lipschitz
selection of $\widetilde{F}$ with

$\|\tilde{f}\|_{\operatorname{Lip}(\widetilde{{\mathcal{M}}},\tilde{\rho})}\leq\lambda_{1}+2\lambda_{2}=3M.$

Let us see that Outcome 1 and Outcome 2 provide the statements given in the
formulation of Theorem 6.20. Indeed, suppose that in case of Outcome 1 there
exists a Lipschitz selection $f$ of $F$ with
$\|f\|_{\operatorname{Lip}({\mathcal{M}})}\leq M$. Then the mapping
$\tilde{f}:\widetilde{{\mathcal{M}}}\to{\bf R}^{2}$ defined by formula (6.45)
is a Lipschitz selection of $\widetilde{F}$ on $\widetilde{{\mathcal{M}}}$
with

$\|\tilde{f}\|_{\operatorname{Lip}(\widetilde{{\mathcal{M}}},\tilde{\rho})}=\|f\|_{\operatorname{Lip}({\mathcal{M}},\rho)}\leq
M,$

a contradiction.

We turn to Outcome 2. We know that the mapping
$\tilde{f}:\widetilde{{\mathcal{M}}}\to{\bf R}^{2}$ is Lipschitz with respect
to the pseudometric $\tilde{\rho}$. Therefore, thanks to part (ii) of Claim
6.21, there exists a unique mapping $f:{\mathcal{M}}\to{\bf R}^{2}$ satisfying
(6.45) such that $f$ is a Lipschitz selection of $F$. Furthermore, in this
case equality (6.46) holds proving that

$\|f\|_{\operatorname{Lip}({\mathcal{M}})}=\|\tilde{f}\|_{\operatorname{Lip}(\widetilde{{\mathcal{M}}},\tilde{\rho})}\leq
3M.$

Thus, both the statement of Outcome 1 and the statement of Outcome 2 hold.

Finally, let us estimate the running time of the $\vec{\lambda}$-Projection
Algorithm with $\vec{\lambda}=(M,M)$ which produces Outcome 1 and Outcome 2.
As we have noted at the beginning of Remark 6.16, the running time of the
$\vec{\lambda}$-Projection Algorithm is $O(N^{3})$ provided
$F:{\mathcal{M}}\to{\mathcal{H}}{\mathcal{P}}({\bf R}^{2})$ and
$\\#{\mathcal{M}}=N$. (As we have noted in this remark, this result will be
proved in [35].) We also know that the pseudometric space
$\widetilde{\mathfrak{M}}=(\widetilde{{\mathcal{M}}},\tilde{\rho})$ contains
at most $L\cdot(\\#{\mathcal{M}})$ elements. Therefore, the $(M,M)$-Projection
Algorithm produces Outcome 1 and Outcome 2, using at most $O(L^{3}N^{3})$
computer operations.

The proof of the theorem is complete. $\blacksquare$

Comparing the results of Theorem 6.20 and Theorem 6.22, we ask the following
question: Let ${\mathcal{M}}=E$ where $E$ is a finite subset of ${\bf R}^{n}$
with $\\#E=N$, and let $\rho$ be the Euclidean metric in ${\bf R}^{n}$. Does
there exist an algorithm which produces Outcome 1 and Outcome 2 in Theorem
6.22 and uses $O(N\log N)$ computer operations as in Theorem 6.20? We will
concern this problem in paper [35].

The last result of this section is the following theorem.

###### Theorem 6.23

Let $L$ be a positive integer. Let ${\mathfrak{M}}=({\mathcal{M}},\rho)$ be a
finite metric space with $\\#{\mathcal{M}}=N$.

There exists an algorithm with $O(L^{3}N^{3})$ running time, which, given
$F:{\mathcal{M}}\to{\mathscr{P}}_{L}({\bf R}^{2})$, produces its Lipschitz
selection with Lipschitz seminorm at most $5|F|_{{\mathfrak{M}}}$.

Proof. Let
$\widetilde{F}:\widetilde{{\mathcal{M}}}\to{\mathcal{H}}{\mathcal{P}}({\bf
R}^{2})$ be the set-valued mapping defined by (6.44). Let
$f:{\mathcal{M}}\to{\bf R}^{2}$ be a selection of $F$. Because
${\mathfrak{M}}=({\mathcal{M}},\rho)$ is a finite metric space, $f$ is
Lipschitz. Part (i) of Claim 6.21 tells us that the mapping
$\tilde{f}:\widetilde{{\mathcal{M}}}\to{\bf R}^{2}$ defined by formula (6.45)
is a Lipschitz (with respect to $\tilde{\rho}$) selection of $\widetilde{F}$.
Hence, $|\widetilde{F}|_{\widetilde{\mathfrak{M}}}<\infty$ so that, thanks to
(6.19), $\Lambda_{{\mathcal{R}}}(\widetilde{F})<\infty$.

Part (iv) of Theorem 6.7 tells us that in this case the
$\vec{\lambda}$-Projection Algorithm with

$\vec{\lambda}=(\,3\Lambda_{{\mathcal{R}}}(\widetilde{F}),\Lambda_{{\mathcal{R}}}(\widetilde{F})\,)$

produces the outcome “Success” and returns the Lipschitz selection
$\tilde{f}=f_{\vec{\lambda};\widetilde{F}}$ of $\widetilde{F}$ with Lipschitz
seminorm
$\|\tilde{f}\|_{\operatorname{Lip}(\widetilde{{\mathcal{M}}},\tilde{\rho})}\leq
5|\widetilde{F}|_{\widetilde{\mathfrak{M}}}$.

In Remark 6.17 we have shown the main ideas of an algorithm which produces the
mapping $\tilde{f}$ in $O((\\#\widetilde{{\mathcal{M}}})^{3})=O(L^{3}N^{3})$
running time. (A detailed description and justification of this algorithm
based on the results of the works [24] and [9] will be done in [35].)

We note that, thanks to part (ii) of Claim 6.21, there exists a (unique)
mapping $f:{\mathcal{M}}\to{\bf R}^{2}$ satisfying (6.45). This mapping is a
Lipschitz selection of $F$ with
$\|f\|_{\operatorname{Lip}({\mathcal{M}})}=\|\tilde{f}\|_{\operatorname{Lip}(\widetilde{{\mathcal{M}}},\tilde{\rho})}$.

Hence, $\|f\|_{\operatorname{Lip}({\mathcal{M}})}\leq
5|\widetilde{F}|_{\widetilde{\mathfrak{M}}}$. But, thanks to part (i) of Claim
6.21, $|\widetilde{F}|_{\widetilde{\mathfrak{M}}}\leq|F|_{{\mathfrak{M}}}$
proving the required inequality $\|f\|_{\operatorname{Lip}({\mathcal{M}})}\leq
5|F|_{{\mathfrak{M}}}$. It is also clear that, thanks to formula (6.45), we
can construct the mapping $f$ using the same number of computer operation as
when constructing the mapping $\tilde{f}$, i.e., at most $O(L^{3}N^{3})$.

The proof of the theorem is complete. $\blacksquare$

##  7\. Lipschitz selections and iterations of balanced refinements.

7.1 The Stabilization Principle for balanced refinements of set-valued
mappings.

In Section 6, we studied a number of efficient algorithms which provide a
solution to Problem 1.2. These algorithms are based on the Projection
Algorithm introduced in Section 6.1.

In the next section, we present another approach to Problem 1.2 based on the
so-called Iterative Algorithm for Lipschitz selections. This algorithm relies
on the results of a recent author’s paper [34]. More specifically, the
Iterative Algorithm is a new constructive and nearly optimal algorithm for
Lipschitz selections based on an interesting property of successive balanced
refinements of set-valued mappings. We refer to this property as the
Stabilization Principle for balanced refinements.

Let us formulate the Stabilization Principle for the special case of the space
$X=\ell^{2}_{\infty}$. Given constants
$\lambda_{1},\lambda_{2},\lambda_{3}\geq 0,$ and a set-valued mapping
$F:{\mathcal{M}}\to\operatorname{Conv}({\bf R}^{2})$, we introduce the
following mappings:

$\displaystyle
F^{[1]}[x:\lambda_{1}]=\bigcap_{z\in{\mathcal{M}}}\big{\\{}F(z)+\lambda_{1}\,\rho(x,z)\,Q_{0}\big{\\}},~{}~{}~{}~{}x\in{\mathcal{M}},$
(7.1) $\displaystyle
F^{[2]}[x:\lambda_{1},\lambda_{2}]=\bigcap_{z\in{\mathcal{M}}}\big{\\{}F^{[1]}[z:\lambda_{1}]+\lambda_{2}\,\rho(x,z)\,Q_{0}\big{\\}},~{}~{}~{}~{}x\in{\mathcal{M}}.$
(7.2)

and

$\displaystyle
F^{[3]}[x:\lambda_{1},\lambda_{2},\lambda_{3}]=\bigcap_{z\in{\mathcal{M}}}\big{\\{}F^{[2]}[z:\lambda_{1}]+\lambda_{3}\,\rho(x,z)\,Q_{0}\big{\\}},~{}~{}~{}~{}x\in{\mathcal{M}}.$
(7.3)

Thus, the mapping $F^{[1]}[\cdot:\lambda_{1}]$ is the $\lambda_{1}$-balanced
refinement of $F$. See (6.1). We refer to the mapping
$F^{[2]}[\cdot:\lambda_{1},\lambda_{2}]:{\mathcal{M}}\to\operatorname{Conv}({\bf
R}^{2})\cup\\{\emptyset\\}$ as the second order
$(\lambda_{1},\lambda_{2})$-balanced refinement of $F$. Accordingly, we refer
to the mapping
$F^{[3]}[\cdot:\lambda_{1},\lambda_{2},\lambda_{3}]:{\mathcal{M}}\to\operatorname{Conv}({\bf
R}^{2})\cup\\{\emptyset\\}$ as the third order
$(\lambda_{1},\lambda_{2},\lambda_{3})$-balanced refinement of $F$.

Clearly,

$\displaystyle F^{[3]}[x:\lambda_{1},\lambda_{2},\lambda_{3}]\subset
F^{[2]}[x:\lambda_{1},\lambda_{2}]\subset F^{[1]}[x:\lambda_{1}]$ (7.4)

for every $\lambda_{1},\lambda_{2},\lambda_{3}\geq 0$ and every
$x\in{\mathcal{M}}$.

###### Theorem 7.1

(The Stabilization Principle for $\ell^{2}_{\infty}$) Let
${\mathfrak{M}}=({\mathcal{M}},\rho)$ be a pseudometric space, and let
$\lambda\geq 0$. Let $F:{\mathcal{M}}\to\operatorname{Conv}({\bf R}^{2})$ be a
set-valued mapping such that for every subset
${\mathcal{M}}^{\prime}\subset{\mathcal{M}}$ with
$\\#{\mathcal{M}}^{\prime}\leq 4$, the restriction
$F|_{{\mathcal{M}}^{\prime}}$ of $F$ to ${\mathcal{M}}^{\prime}$ has a
Lipschitz selection with Lipschitz seminorm at most $\lambda$. Suppose that
either ${\mathcal{M}}$ is finite or $F:{\mathcal{M}}\to{\mathcal{K}}({\bf
R}^{2})$.

Then

$\displaystyle F^{[2]}[x:\lambda,3\lambda]\neq\emptyset~{}~{}~{}~{}\text{for
every}~{}~{}~{}~{}x\in{\mathcal{M}}.$ (7.5)

Furthermore,

$\displaystyle
F^{[3]}[x:\lambda,3\lambda,15\lambda]=F^{[2]}[x:\lambda,3\lambda]~{}~{}~{}~{}\text{for
every}~{}~{}~{}~{}x\in{\mathcal{M}}.$ (7.6)

In particular, Theorem 7.1 implies the following property: the sequence of the
successive refinements defined by

$\displaystyle
F^{[k+1]}[x:\lambda_{1},...,\lambda_{k+1}]=\bigcap_{z\in{\mathcal{M}}}\big{\\{}F^{[k]}[z:\lambda_{1},...,\lambda_{k}]+\lambda_{k+1}\rho(x,z)B_{X}\big{\\}},~{}~{}~{}~{}x\in{\mathcal{M}},$
(7.7)

stabilizes at the third step of this procedure provided $F$ satisfies the
hypothesis of this theorem and $\lambda_{1}=\lambda$, $\lambda_{2}=3\lambda$
and

$\displaystyle\lambda_{k}=\lambda_{3}=15\lambda~{}~{}~{}\text{for
all}~{}~{}~{}k\geq 3.$ (7.8)

In other words, $F^{[k]}=F^{[2]}$ on ${\mathcal{M}}$ for every $k=3,4,...\,$.
Indeed, if $F^{[k]}=F^{[2]}$ for some $k\geq 3$, then, thanks to (7.7), (7.8)
and (7.6), for every $x\in{\mathcal{M}}$, we have

$F^{[k+1]}[x:\lambda_{1},...,\lambda_{k+1}]=\bigcap_{z\in{\mathcal{M}}}\big{\\{}F^{[2]}[z:\lambda_{1},\lambda_{2}]+\lambda_{3}\rho(x,z)B_{X}\big{\\}}=F^{[3]}[x:\lambda_{1},\lambda_{2},\lambda_{3}]=F^{[2]}[x:\lambda_{1},\lambda_{2}].$

Also, let us note that, thanks to (7.1), (7.2), (7.3) and (7.4), equality
(7.6) is equivalent to the following inequality:

$\displaystyle\operatorname{d_{H}}(F^{[2]}[x:\lambda,3\lambda],F^{[2]}[y:\lambda,3\lambda])\leq
15\lambda\,\rho(x,y)~{}~{}~{}~{}\text{for
every}~{}~{}~{}~{}x,y\in{\mathcal{M}}.$ (7.9)

(Recall that the sign $\operatorname{d_{H}}$ denotes the Hausdorff distance
between sets. See (2.1).)

###### Remark 7.2

Theorem 7.1 is a slight generalization of the main result of the work [34],
Theorem 1.9, for the case of the space $X=\ell^{2}_{\infty}$. More
specifically, in this theorem we give a proof of the Stabilization Principle
only for set-valued mappings from ${\mathcal{M}}$ into ${\mathcal{K}}({\bf
R}^{2})$.

However, obvious changes to this proof show that this principle also holds for
an arbitrary finite pseudometric space ${\mathfrak{M}}=({\mathcal{M}},\rho)$
and arbitrary set-valued mapping $F:{\mathcal{M}}\to\operatorname{Conv}({\bf
R}^{2})$. These changes are mainly related to the classical Helly intersection
theorem in ${\bf R}^{2}$. It known that this theorem is true both for
arbitrary families of convex compacts (this version was used in [34]) and
arbitrary finite collections of convex sets in ${\bf R}^{2}$.

This enables us to add to the hypotheses of Lemma 3.4 in [34] the case of a
finite collection of closed sets. Using this version of this lemma in the
proof given in [34], we obtain the required generalization of the
Stabilization Principle to the case of a finite set ${\mathcal{M}}$ and a
mapping $F$ from ${\mathcal{M}}$ into $\operatorname{Conv}({\bf R}^{2})$.
$\blacktriangleleft$

7.2 The Iterative Algorithm for set-valued mappings.

Let ${\mathfrak{M}}=({\mathcal{M}},\rho)$ be a finite pseudometric space. In
this section we describe the Iterative Algorithm for Lipschitz selections.
This geometrical algorithm relies on Theorem 7.1.

An important parameter of the Iterative Algorithm is the constant
$\Lambda^{({\mathcal{F}}{\mathcal{P}})}(F)$ introduced in Section 6.3, see
Definition 6.12.

Let ${\mathfrak{T}}$ be either the family ${\mathcal{K}}({\bf R}^{2})$ or the
family ${\mathcal{H}}{\mathcal{P}}({\bf R}^{2})$. (See (1.3) and (1.4).)

###### Algorithm 7.3

(The Iterative Algorithm for nearly optimal Lipschitz selections.)

Given a finite pseudometric space ${\mathfrak{M}}=({\mathcal{M}},\rho)$ and a
set-valued mapping $F:{\mathcal{M}}\to{\mathfrak{T}}$, the Iterative Algorithm
produces a nearly optimal Lipschitz selection of $F$ (the outcome “Success”)
or stops (the outcome “No go”).

This procedure includes the following three steps.

STEP 1. At this step we compute the constant
$\Lambda^{({\mathcal{F}}{\mathcal{P}})}(F)$. If it turns out that

$\Lambda^{({\mathcal{F}}{\mathcal{P}})}(F)=+\infty,$

the algorithm produces the outcome “No go” and stops. In this case, we
guarantee that $F$ does not have a Lipschitz selection.

STEP 2. At this and the next steps, we assume that the constant
$\Lambda^{({\mathcal{F}}{\mathcal{P}})}(F)<\infty$.

We fix a constant

$\lambda\in[\Lambda^{({\mathcal{F}}{\mathcal{P}})}(F),+\infty),$

and, for all $x\in{\mathcal{M}}$, construct the $\lambda$-balanced refinement
of $F$,

$\displaystyle
F^{[1]}[x:\lambda]=\bigcap_{z\in{\mathcal{M}}}\big{\\{}F(z)+\lambda\,\rho(x,z)Q_{0}\big{\\}}.$
(7.10)

Then, for every $x\in{\mathcal{M}}$, we construct the second order
$(\lambda,3\lambda)$-balanced refinement of $F$, i.e., the set

$\displaystyle
F^{[2]}[x:\lambda,3\lambda]=\bigcap_{z\in{\mathcal{M}}}\big{\\{}F^{[1]}[z:\lambda]+3\lambda\rho(x,z)Q_{0}\big{\\}}.$
(7.11)

We define a set ${\mathscr{F}}[x:\lambda]$ by letting

$\displaystyle{\mathscr{F}}[x:\lambda]=F^{[2]}[x:\lambda,3\lambda]\cap
Q(0,2r_{x})$ (7.12)

where

$\displaystyle
r_{x}=\operatorname{dist}\left(0,F^{[2]}[x:\lambda,3\lambda]\right).$ (7.13)

STEP 3. Finally, we define a mapping $f^{[\lambda;F]}:{\mathcal{M}}\to{\bf
R}^{2}$ by the formula

$\displaystyle
f^{[\lambda;F]}(x)=\operatorname{center}(\,\Pi_{\lambda,F}(x)),~{}~{}~{}~{}~{}~{}x\in{\mathcal{M}},$
(7.14)

where

$\displaystyle\Pi_{\lambda,F}(x)={\mathcal{H}}[{\mathscr{F}}[x:\lambda]].$
(7.15)

Thus, $\Pi_{\lambda,F}(x)$ is the rectangular hull of the set
${\mathscr{F}}[x:\lambda]$. See (2.11). We also recall that
$\operatorname{center}(S)$ denotes the center of a centrally symmetric set
$S\subset{\bf R}^{2}$.

See Fig. 19.

Fig. 19: The $(\lambda;F)$-Iterative Algorithm.

At this stage, Algorithm 7.3 produces the outcome “Success” and stops.
$\blacksquare$

We refer to Algorithm 7.3 as the $(\lambda;F)$-Iterative Algorithm.

###### Remark 7.4

Let if ${\mathfrak{M}}=({\mathcal{M}},\rho)$ be a finite metric space and let
$F:{\mathcal{M}}\to\operatorname{Conv}({\bf R}^{2})$ be a set-valued mapping.
Clearly, in this case any selection $f$ of $F$ is Lipschitz. In particular, in
this case, the constant $\Lambda^{({\mathcal{F}}{\mathcal{P}})}(F)<+\infty$.

Thus, if $\rho$ is a metric on a finite set ${\mathcal{M}}$, and
$\lambda\in[\Lambda^{({\mathcal{F}}{\mathcal{P}})}(F),+\infty)$, the
$(\lambda;F)$-Iterative Algorithm 7.3 always produces the outcome “Success”.
Cf. Remark 6.9, part (i). $\blacktriangleleft$

###### Theorem 7.5

Let ${\mathfrak{M}}=({\mathcal{M}},\rho)$ be a finite pseudometric space. Let
${\mathfrak{T}}$ be either the family ${\mathcal{K}}({\bf R}^{2})$ or the
family ${\mathcal{H}}{\mathcal{P}}({\bf R}^{2})$, and let
$F:{\mathcal{M}}\to{\mathfrak{T}}$ be a set-valued mapping.

If Algorithm 7.3 produces the outcome “No go” (i.e., if
$\Lambda^{({\mathcal{F}}{\mathcal{P}})}(F)=+\infty$, see STEP 1), the set-
valued mapping $F$ does not have a Lipschitz selection.

Otherwise, given a constant
$\lambda\in[\Lambda^{({\mathcal{F}}{\mathcal{P}})}(F),+\infty)$, the
$(\lambda;F)$-Iterative Algorithm produces the outcome “Success” and returns
the mapping $f^{[\lambda;F]}:{\mathcal{M}}\to{\bf R}^{2}$ defined by formula
(7.14). This mapping has the following properties:

($\bigstar{\mathscr{A}}$) The mapping $f^{[\lambda;F]}$ is well defined. This
means the following: (i) For every $x\in{\mathcal{M}}$, the sets
$F^{[1]}[x:\lambda]$ and $F^{[2]}[x:\lambda,3\lambda]$ are non-empty; (ii) The
rectangle $\Pi_{\lambda,F}(x)={\mathcal{H}}[{\mathscr{F}}[x:\lambda]]$ (see
(7.12) and (7.13)) is a non-empty bounded subset of ${\bf R}^{2}$.

($\bigstar{\mathscr{B}}$) $f^{[\lambda;F]}$ is a Lipschitz selection of $F$
with the Lipschitz seminorm
$\|f^{[\lambda;F]}\|_{\operatorname{Lip}({\mathcal{M}})}\leq\gamma\lambda$
with $\gamma=420$.

Proof. Suppose that $\Lambda^{({\mathcal{F}}{\mathcal{P}})}(F)=+\infty$, and
at the same time there exists a Lipschitz selection $f$ of $F$. Then, for
every subset ${\mathcal{M}}^{\prime}\subset{\mathcal{M}}$ with
$\\#{\mathcal{M}}^{\prime}\leq 4$, the mapping $f|_{{\mathcal{M}}^{\prime}}$
is a Lipschitz selection of the restriction $F|_{{\mathcal{M}}^{\prime}}$ of
$F$ to ${\mathcal{M}}^{\prime}$ with
$\|f|_{{\mathcal{M}}^{\prime}}\|_{\operatorname{Lip}({\mathcal{M}}^{\prime})}\leq\lambda$
where $\lambda=\|f\|_{\operatorname{Lip}({\mathcal{M}})}$. Therefore, thanks
to Definition (6.12),
$\lambda\in{\mathcal{L}}^{({\mathcal{F}}{\mathcal{P}})}(F)$ so that, thanks to
(6.35), $\Lambda^{({\mathcal{F}}{\mathcal{P}})}(F)<\infty$, a contradiction.

This proves that if Algorithm 7.3 produces the outcome “No go”, the set-valued
mapping $F$ does not have a Lipschitz selection.

Now, let us assume that $\Lambda^{({\mathcal{F}}{\mathcal{P}})}(F)<\infty$ and
$\lambda\in[\Lambda^{({\mathcal{F}}{\mathcal{P}})}(F),+\infty)$. Prove that in
this case the mapping $f^{[\lambda;F]}:{\mathcal{M}}\to{\bf R}^{2}$ defined by
(7.14) has properties ($\bigstar{\mathscr{A}}$) and ($\bigstar{\mathscr{B}}$).

Prove part (i) of the statement ($\bigstar{\mathscr{A}}$). Thanks to Lemma
6.13, the constant
$\Lambda^{({\mathcal{F}}{\mathcal{P}})}(F)\in{\mathcal{L}}^{({\mathcal{F}}{\mathcal{P}})}(F)$,
see Definition 6.12. Therefore,
$\lambda\in{\mathcal{L}}^{({\mathcal{F}}{\mathcal{P}})}(F)$ as well, so that,
thanks to Definition 6.12, for every subset
${\mathcal{M}}^{\prime}\subset{\mathcal{M}}$ with
$\\#{\mathcal{M}}^{\prime}\leq 4$, the restriction
$F|_{{\mathcal{M}}^{\prime}}$ of $F$ to ${\mathcal{M}}^{\prime}$ has a
Lipschitz selection $f_{{\mathcal{M}}^{\prime}}$ with
$\|f_{{\mathcal{M}}^{\prime}}\|_{\operatorname{Lip}({\mathcal{M}}^{\prime})}\leq\lambda$.

We also recall that ${\mathcal{M}}$ is finite. Therefore, the pseudometric
space ${\mathfrak{M}}=({\mathcal{M}},\rho)$ and the constant $\lambda$ satisfy
the hypothesis of Theorem 7.1. This theorem tells us that property (7.5)
holds, i.e., the set

$\displaystyle F^{[2]}[x:\lambda,3\lambda]\neq\emptyset~{}~{}~{}~{}\text{for
every}~{}~{}~{}~{}x\in{\mathcal{M}}.$ (7.16)

But, thanks to (7.4), $F^{[2]}[x:\lambda,3\lambda]\subset F^{[1]}[x:\lambda]$
so that $F^{[1]}[x:\lambda]\neq\emptyset$ as well. Thus, part (i) of
($\bigstar{\mathscr{A}}$) holds.

Let us note that part (ii) of ($\bigstar{\mathscr{A}}$) is immediate from part
(i). Indeed, thanks to (7.16), the set ${\mathscr{F}}[x:\lambda]$ defined by
(7.12) and (7.13) is a non-empty. Futhermore, ${\mathscr{F}}[x:\lambda]$ is
bounded. Therefore, its rectangular hull, the rectangular
$\Pi_{\lambda,F}(x)$, is also non-empty and bounded. In particular, the center
of $\Pi_{\lambda,F}(x)$ is well defined so that the mapping $f^{[\lambda;F]}$
is well defined on ${\mathcal{M}}$. See (7.14).

Let us prove property ($\bigstar{\mathscr{B}}$). Let

$\displaystyle{\mathscr{G}}(x)=F^{[2]}[x:\lambda,3\lambda],~{}~{}~{}x\in{\mathcal{M}}.$
(7.17)

Then, thanks to (7.9),

$\displaystyle\operatorname{d_{H}}({\mathscr{G}}(x),{\mathscr{G}}(y))\leq
15\lambda\,\rho(x,y)~{}~{}~{}~{}\text{for
every}~{}~{}~{}~{}x,y\in{\mathcal{M}}.$ (7.18)

In these settings, definitions (7.12) and (7.13) read as follows:

$\displaystyle{\mathscr{F}}[x:\lambda]={\mathscr{G}}(x)\cap
Q(0,2r_{x})~{}~{}~{}~{}~{}~{}\text{where}~{}~{}r_{x}=\operatorname{dist}\left(0,{\mathscr{G}}(x)\right).$
(7.19)

Let us estimate the Hausdorff distance between the sets
${\mathscr{F}}[x:\lambda]$ and ${\mathscr{F}}[y:\lambda]$. We will do this
with the help of the following result:

Let $C_{1},C_{2}\subset{\bf R}^{2}$ be convex sets. Given $i=1,2$, let
$a_{i}\in{\bf R}^{2}$, $r_{i}\geq 0$, and let $Q(a_{i},r_{i})$ be a square in
${\bf R}^{2}$, see (2.5). Suppose that $C_{i}\cap
Q(a_{i},r_{i})\neq\emptyset$, $i=1,2$. Then

$\displaystyle\operatorname{d_{H}}(C_{1}\cap Q(a_{1},2r_{1}),C_{2}\cap
Q(2a_{2},r_{2}))\leq
14\,(\operatorname{d_{H}}(C_{1},C_{2})+\|a_{1}-a_{2}\|+|r_{1}-r_{2}|).$ (7.20)

See [27, Theorem 4], and also [31, Lemma 3.9].

We note, that, thanks to (7.19),

${\mathscr{G}}(x)\cap
Q(0,r_{x})\neq\emptyset~{}~{}~{}~{}\text{and}~{}~{}~{}~{}{\mathscr{G}}(y)\cap
Q(0,r_{y})\neq\emptyset.$

Therefore, thanks to (7.20),

$\operatorname{d_{H}}({\mathscr{F}}[x:\lambda],{\mathscr{F}}[y:\lambda])=\operatorname{d_{H}}({\mathscr{G}}(x)\cap
Q(0,2r_{x}),{\mathscr{G}}(y)\cap Q(0,2r_{y}))\leq
14\,(\operatorname{d_{H}}({\mathscr{G}}(x),{\mathscr{G}}(y))+|r_{x}-r_{y}|).$

Furthermore, from (7.18), we have

$|r_{x}-r_{y}|=|\operatorname{dist}(0,{\mathscr{G}}(x))-\operatorname{dist}(0,{\mathscr{G}}(y))|\leq\operatorname{d_{H}}({\mathscr{G}}(x),{\mathscr{G}}(y))\leq
15\lambda\,\rho(x,y).$

This inequality and (7.18) imply the following:

$\displaystyle\operatorname{d_{H}}({\mathscr{F}}[x:\lambda],{\mathscr{F}}[y:\lambda])\leq
14\,(15\lambda\,\rho(x,y)+15\lambda\,\rho(x,y))=\gamma\lambda\,\rho(x,y)$
(7.21)

with $\gamma=420$.

We are in a position to prove that $f^{[\lambda;F]}$ is a Lipschitz selection
of $F$ with Lipschitz seminorm at most $\gamma\lambda$. This property easily
follows from (7.21) and the following simple claim proven in [17, Remark 7.1]:
For every compact convex set $S\subset{\bf R}^{2}$, the center of its
rectangular hull belongs to $S$, i.e.,
$\operatorname{center}({\mathcal{H}}[S])\in S$. Furthermore, for every compact
convex sets $S_{1},S_{2}\subset{\bf R}^{2}$, we have

$\displaystyle\|\operatorname{center}({\mathcal{H}}[S_{1}])-\operatorname{center}({\mathcal{H}}[S_{2}])\|\leq\operatorname{d_{H}}(S_{1},S_{2}).$
(7.22)

See also inequality (2.34).

Now, thanks to this claim and definition (7.14), for every
$x\in{\mathcal{M}}$, we have

$f^{[\lambda;F]}(x)=\operatorname{center}(\Pi_{\lambda,F}(x))=\operatorname{center}({\mathcal{H}}[{\mathscr{F}}[x:\lambda]])\in{\mathscr{F}}[x:\lambda]\subset
F^{[2]}[x:\lambda,3\lambda]\subset F(x)$

proving that $f^{[\lambda;F]}$ is a selection of $F$.

Finally, combining (7.14) with inequality (7.22) (where we set
$S_{1}={\mathscr{F}}[x:\lambda]$ and $S_{2}={\mathscr{F}}[y:\lambda]$) and
inequality (7.21), we conclude that
$\|f^{[\lambda;F]}\|_{\operatorname{Lip}({\mathcal{M}})}\leq\gamma\lambda$
with $\gamma=420$.

The proof of the theorem is complete. $\blacksquare$

###### Remark 7.6

Formula (7.14) can be simplified essentially provided

$\displaystyle\text{for some $\bar{x}\in{\mathcal{M}}$ the
set}~{}~{}~{}{\mathscr{G}}(\bar{x})=F^{[2]}[\bar{x}:\lambda,3\lambda]~{}~{}~{}\text{is
bounded.}$ (7.23)

See (7.17). In this case, thanks to (7.18), every set
${\mathscr{G}}(x)=F^{[2]}[x:\lambda,3\lambda]$, $x\in{\mathcal{M}}$, is
bounded.

This enables us to modify STEP 3 of Algorithm 7.3 as follows:

STEP 3′. We define the mapping $f^{[\lambda;F]}:{\mathcal{M}}\to{\bf R}^{2}$
by the formula

$f^{[\lambda;F]}(x)=\operatorname{center}(\,{\mathcal{V}}_{\lambda,F}(x)),~{}~{}~{}~{}~{}~{}x\in{\mathcal{M}},$

where
${\mathcal{V}}_{\lambda,F}(x)={\mathcal{H}}[{\mathscr{G}}(x)]={\mathcal{H}}[F^{[2]}[x:\lambda,3\lambda]]$.
See Fig. 20.

Fig. 20: The $(\lambda;F)$-Iterative Algorithm for bounded sets
$F^{[2]}[x:\lambda,3\lambda]$.

Because ${\mathscr{G}}(x)$ is bounded for every $x\in{\mathcal{M}}$, the set
${\mathcal{V}}_{\lambda,F}(x)={\mathcal{H}}[{\mathscr{G}}(x)]$ is a bounded
rectangle so that the mapping $f^{[\lambda;F]}$ is well defined on
${\mathcal{M}}$.

Following the scheme of the proof of Theorem 7.5, we show that
$f^{[\lambda;F]}$ is a selection of $F$. Furthermore, thanks to (7.18) and
(7.22), we have

$\|f^{[\lambda;F]}(x)-f^{[\lambda;F]}(y)\|=\|\operatorname{center}({\mathcal{H}}[{\mathscr{G}}(x)])-\operatorname{center}({\mathcal{H}}[{\mathscr{G}}(y)])\|\leq\operatorname{d_{H}}({\mathscr{G}}(x),{\mathscr{G}}(y))\leq
15\lambda\rho(x,y)$

proving that

$\displaystyle\|f^{[\lambda;F]}\|_{\operatorname{Lip}({\mathcal{M}})}\leq
15\lambda.$ (7.24)

We note that condition (7.23) holds for every set-valued mapping $F$ from
${\mathcal{M}}$ into the family ${\mathcal{K}}({\bf R}^{2})$. Therefore, in
this important case, we can apply this simplified version of Algorithm 7.3
which produces a Lipschitz selection of $F$ with Lipschitz seminorm satisfying
inequality (7.24). $\blacktriangleleft$

###### Remark 7.7

We recall Definitions 6.5 and 6.12 of the constants
$\Lambda_{{\mathcal{R}}}(F)$ and $\Lambda^{({\mathcal{F}}{\mathcal{P}})}(F)$
respectively. As we have noted in Remark 6.16, in general, given a set-valued
mapping $F:{\mathcal{M}}\to\operatorname{Conv}({\bf R}^{2})$, the precise
calculation of the constants $\Lambda_{{\mathcal{R}}}(F)$ and
$\Lambda^{({\mathcal{F}}{\mathcal{P}})}(F)$ is a rather difficult technical
problem. Nevertheless, comparing these constants, we note that the constant
$\Lambda_{{\mathcal{R}}}(F)$ is defined in a more constructive way than
$\Lambda^{({\mathcal{F}}{\mathcal{P}})}(F)$. Moreover, Remark 6.17 tells us
there exists an algorithm which given
$F:{\mathcal{M}}\to{\mathcal{H}}{\mathcal{P}}({\bf R}^{2})$ calculates
$\Lambda_{{\mathcal{R}}}(F)$ using at most $O(N^{3})$ computer operations.
(Here $N=\\#{\mathcal{M}}$.)

Thus, in applications, it would be preferable to express Algorithm 7.3 in
terms of the constant $\Lambda_{{\mathcal{R}}}(F)$ rather than
$\Lambda^{({\mathcal{F}}{\mathcal{P}})}(F)$.

An appropriate choice of the constant $\lambda$ at STEP 2 of this algorithm
enables us to do this. Indeed, suppose we have calculated
$\Lambda_{{\mathcal{R}}}(F)$ up to a constant $\eta\geq 1$. From inequalities
(6.37) and (6.38), we have $\Lambda^{({\mathcal{F}}{\mathcal{P}})}(F)\leq
5\Lambda_{{\mathcal{R}}}(F)$. From this inequality it follows that the
parameter

$\displaystyle\lambda=5\eta\Lambda_{{\mathcal{R}}}(F)$ (7.25)

belongs to the interval $[\Lambda^{({\mathcal{F}}{\mathcal{P}})}(F),+\infty)$.

Therefore, thanks to Theorem 7.5, if $\Lambda_{{\mathcal{R}}}(F)<\infty$, the
$(\lambda;F)$-Iterative Algorithm 7.3 produces the outcome “Success” and
returns a Lipschitz selection of $F$ with Lipschitz seminorm at most
$\gamma\lambda=5\gamma\eta\Lambda_{{\mathcal{R}}}(F)$. (Recall that
$\gamma=420$). $\blacktriangleleft$

Let ${\mathfrak{M}}=({\mathcal{M}},\rho)$ be a finite pseudometric space,
$N=\\#{\mathcal{M}}$, and let
$F:{\mathcal{M}}\to{\mathcal{H}}{\mathcal{P}}({\bf R}^{2})$ be a set-valued
mapping. Let us see, how with the help of the $(\lambda;F)$-Iterative
Algorithm 7.3 with $\lambda$ defined by (7.25) one can produce a nearly
optimal Lipschitz selection of $F$ using at most $O(N^{3})$ computer
operations.

First of all, Remark 6.17 tells us that there exists an algorithm for
calculating the constant $\Lambda_{{\mathcal{R}}}(F)$ with $O(N^{3})$ running
time. Therefore, we can calculate the constant $\lambda$ from (7.25) using at
most $O(N^{3})$ computer operations.

Let us estimate the running time of the $(\lambda;F)$-Iterative Algorithm 7.3.

###### Proposition 7.8

Let $F:{\mathcal{M}}\to{\mathcal{H}}{\mathcal{P}}({\bf R}^{2})$ be a set
valued mapping defined on a finite pseudometric space
${\mathfrak{M}}=({\mathcal{M}},\rho)$. Suppose that the constant
$\Lambda^{({\mathcal{F}}{\mathcal{P}})}(F)<\infty$.

If $\lambda\in[\Lambda^{({\mathcal{F}}{\mathcal{P}})}(F),+\infty)$, then the
$(\lambda;F)$-Iterative Algorithm 7.3 produces the outcome “Success” and
returns the mapping $f^{[\lambda;F]}:{\mathcal{M}}\to{\bf R}^{2}$ (see (7.14))
with
$\|f^{[\lambda;F]}\|_{\operatorname{Lip}({\mathcal{M}})}\leq\gamma\lambda$
using at most $O(N^{2})$ computer operations. (Here $\gamma$ is an absolute
constant.)

The proof of this proposition relies on a formula for the set
$F^{[2]}[x:\lambda_{1},\lambda_{2}]$, see (7.2), which we present in Lemma 7.9
below.

Before stating this lemma, let us recall the definitions of some objects from
the Projection Algorithm 6.1. These are the set $F^{[1]}[x:\lambda_{1}]$,
i.e., the $\lambda_{1}$-balanced refinement of $F$ defined by (6.2), its
rectangular hull, the set
${\mathcal{T}}_{F,\lambda_{1}}(x)={\mathcal{H}}[F^{[1]}[x:\lambda_{1}]]$, see
(6.3), and, finally, the $\lambda_{2}$-balanced refinement of
${\mathcal{T}}_{F,\lambda_{1}}$, i.e., the rectangle
${\mathcal{T}}^{[1]}_{F,\lambda_{1}}[x:\lambda_{2}]$ defined by formula (6.4).

###### Lemma 7.9

Let ${\mathfrak{M}}=({\mathcal{M}},\rho)$ be a finite pseudometric space and