@inproceedings{backurs2021two-sided,
author = {Backurs, Arturs and Mahabadi, Sepideh and Makarychev, Konstantin and , Yury Makarychev},
title = {Two-sided Kirszbraun Theorem},
year = {2021},
month = {June},
abstract = { 

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 R^m. The Kirszbraun theorem states that the map f can be extended to a 1-Lipschitz map ~f from Y to R^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 + eps)-Lipschitz outer extension ~f : Y -> R^[m'] that does not decrease distances more than "necessary". Namely, ||~f(x) - ~f(y)|| ≥ c sqrt(eps) min(||x - y||, inf_[a,b in 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 in 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 in 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)||.},
url = {http://approjects.co.za/?big=en-us/research/publication/two-sided-kirszbraun-theorem/},
}