Abstract
In this paper, we prove a twosided variant of the Kirszbraun theorem. Consider an arbitrary subset X of Euclidean space and its superset Y. Let f be a 1Lipschitz map from X to ℝ^m. The Kirszbraun theorem states that the map f can be extended to a 1Lipschitz 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 + ε)Lipschitz outer extension f̃:Y → ℝ^{m'} that does not decrease distances more than "necessary". Namely, ‖f̃(x)  f̃(y)‖ ≥ c √{ε} min(‖xy‖, inf_{a,b ∈ X} (‖x  a‖ + ‖f(a)  f(b)‖ + ‖by‖)) for some absolutely constant c > 0. This bound is asymptotically optimal, since no LLipschitz extension g can have ‖g(x)  g(y)‖ > L min(‖xy‖, inf_{a,b ∈ X} (‖x  a‖ + ‖f(a)  f(b)‖ + ‖by‖)) 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)‖.
BibTeX  Entry
@InProceedings{backurs_et_al:LIPIcs.SoCG.2021.13,
author = {Backurs, Arturs and Mahabadi, Sepideh and Makarychev, Konstantin and Makarychev, Yury},
title = {{TwoSided Kirszbraun Theorem}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {13:113:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771849},
ISSN = {18688969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13812},
URN = {urn:nbn:de:0030drops138129},
doi = {10.4230/LIPIcs.SoCG.2021.13},
annote = {Keywords: Kirszbraun theorem, Lipschitz map, Outerextension, Twosided extension}
}
Keywords: 

Kirszbraun theorem, Lipschitz map, Outerextension, Twosided extension 
Collection: 

37th International Symposium on Computational Geometry (SoCG 2021) 
Issue Date: 

2021 
Date of publication: 

02.06.2021 