# Two-sided Kirszbraun theorem

Arturs Backurs*, Sepideh Mahabadi, Konstantin Makarychev, Yury Makarychev

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

## 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 ℝ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∥, a,b inf ∈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)∥ > Lmin(∥x − y∥, infa,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)∥.

Original language English (US) 37th International Symposium on Computational Geometry, SoCG 2021 Kevin Buchin, Eric Colin de Verdiere Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing 9783959771849 https://doi.org/10.4230/LIPIcs.SoCG.2021.13 Published - Jun 1 2021 37th International Symposium on Computational Geometry, SoCG 2021 - Virtual, Buffalo, United StatesDuration: Jun 7 2021 → Jun 11 2021

### Publication series

Name Leibniz International Proceedings in Informatics, LIPIcs 189 1868-8969

### Conference

Conference 37th International Symposium on Computational Geometry, SoCG 2021 United States Virtual, Buffalo 6/7/21 → 6/11/21

## Keywords

• Kirszbraun theorem
• Lipschitz map
• Outer-extension
• Two-sided extension

• Software

## Fingerprint

Dive into the research topics of 'Two-sided Kirszbraun theorem'. Together they form a unique fingerprint.