2026-08-15T12:05:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13812 2024-03-06T10:52:46Z ddc:004 open_access

Two-Sided Kirszbraun Theorem Backurs, Arturs Mahabadi, Sepideh Makarychev, Konstantin Makarychev, Yury Kirszbraun theorem Lipschitz map Outer-extension Two-sided extension 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 + ε)-Lipschitz outer extension f̃:Y → ℝ^{m'} that does not decrease distances more than "necessary". Namely, ‖f̃(x) - f̃(y)‖ ≥ c √{ε} 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)‖. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Arturs Backurs and Sepideh Mahabadi and Konstantin Makarychev and Yury Makarychev 2021 Is Part Of LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2021.13 urn:nbn:de:0030-drops-138129 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.13 eng https://creativecommons.org/licenses/by/4.0/legalcode