Two-sided Kirszbraun Theorem

In this paper, we prove a two-sided variant of the Kirszbraun theorem. Consider an arbitrary subset X of Euclidean space and its superset Y. Let f be a 1-Lipschitz map from X to ℝ^m. The Kirszbraun theorem states that the map f can be extended to a 1-Lipschitz map f from Y to ℝ^m. While the extension f does not increase distances between points, there is no guarantee that it does not decrease distances significantly. In fact, f may even map distinct points to the same point (that is, it can infinitely decrease some distances). However, we prove that there exists a (1 + e)-Lipschitz outer extension f:Y → ℝ^{m'} that does not decrease distances more than "necessary". Namely, ‖f(x) - f(y)‖ ≥ c √{e} min(‖x-y‖, inf_{a,b ∈ X} (‖x - a‖ + ‖f(a) - f(b)‖ + ‖b-y‖)) for some absolutely constant c > 0. This bound is asymptotically optimal, since no L-Lipschitz extension g can have ‖g(x) - g(y)‖ > L min(‖x-y‖, inf_{a,b ∈ X} (‖x - a‖ + ‖f(a) - f(b)‖ + ‖b-y‖)) even for a single pair of points x and y. In some applications, one is interested in the distances ‖f(x) - f(y)‖ between images of points x,y ∈ Y rather than in the map f itself. The standard Kirszbraun theorem does not provide any method of computing these distances without computing the entire map f first. In contrast, our theorem provides a simple approximate formula for distances ‖f(x) - f(y)‖.