TY - GEN

T1 - Two-sided Kirszbraun theorem

AU - Backurs, Arturs

AU - Mahabadi, Sepideh

AU - Makarychev, Konstantin

AU - Makarychev, Yury

N1 - Funding Information:
Funding Arturs Backurs: Supported in part by NSF award CCF-2006806. Konstantin Makarychev: Supported in part by NSF awards CCF-1955351 and HDR TRIPODS CCF-1934931. Yury Makarychev: Supported in part by NSF awards CCF-1718820, CCF-1955173, and HDR TRIPODS CCF-1934843.
Publisher Copyright:
© Arturs Backurs, Sepideh Mahabadi, Konstantin Makarychev, and Yury Makarychev; licensed under Creative Commons License CC-BY 4.0 37th International Symposium on Computational Geometry (SoCG 2021).

PY - 2021/6/1

Y1 - 2021/6/1

N2 - 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)∥.

AB - 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)∥.

KW - Kirszbraun theorem

KW - Lipschitz map

KW - Outer-extension

KW - Two-sided extension

UR - http://www.scopus.com/inward/record.url?scp=85108236823&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85108236823&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.SoCG.2021.13

DO - 10.4230/LIPIcs.SoCG.2021.13

M3 - Conference contribution

AN - SCOPUS:85108236823

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 37th International Symposium on Computational Geometry, SoCG 2021

A2 - Buchin, Kevin

A2 - de Verdiere, Eric Colin

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 37th International Symposium on Computational Geometry, SoCG 2021

Y2 - 7 June 2021 through 11 June 2021

ER -