Efficient Algorithms for Lipschitz Selections of Set-Valued Mappings in ${\mathbf{R}}^2$: long version

Let $F$ be a set-valued mapping from an $N$-element metric space $(\mathcal{M},\rho )$ into the family of all closed half-planes in ${\mathbf{R}}^2$. In this paper, we provide an efficient algorithm for a Lipschitz selection of $F$, i.e., a Lipschitz mapping $f:\mathcal{M}\to {\mathbf{R}}^2$ such that $f(x)\in F(x)$ for all $x\in \mathcal{M}$. Given a constant $\lambda >0$, this algorithm produces the following two outcomes: (1) The algorithm guarantees that there is no Lipschitz selection of $F$ with Lipschitz constant at most $\lambda$; (2) The algorithm returns a Lipschitz selection of $F$ with Lipschitz constant at most $3\lambda$. The total work and storage required by this selection algorithm are at most $C{N}^2$ where $C$ is an absolute constant.