More Like this

1. Two-Sided Kirszbraun Theorem

   https://doi.org/10.4230/LIPIcs.SoCG.2021.13  

   Backurs, Arturs; Mahabadi, Sepideh; Makarychev, Konstantin; Makarychev, Yury (June 2021, Leibniz international proceedings in informatics)

   Buchin, Kevin; Colin de Verdiere, Eric (Ed.)

   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)‖. 

   more » « less
2. Decomposing multitwists

   https://doi.org/10.1007/s11854-023-0301-4  

   Fletcher, Alastair N; Vellis, Vyron (April 2024, Journal d'Analyse Mathématique)

   The Decomposition Problem in the class $$LIP(\S^2)$$ is to decompose any bi-Lipschitz map $$f:\S^2 \to \S^2$$ as a composition of finitely many maps of arbitrarily small isometric distortion. In this paper, we construct a decomposition for certain bi-Lipschitz maps which spiral around every point of a Cantor set $$X$$ of Assouad dimension strictly smaller than one. These maps are constructed by considering a collection of Dehn twists on the Riemann surface $$\S^2 \setminus X$$. The decomposition is then obtained via a bi-Lipschitz path which simultaneously unwinds these Dehn twists. As part of our construction, we also show that $$X \subset \S^2$$ is uniformly disconnected if and only if the Riemann surface $$\S^2 \setminus X$$ has a pants decomposition whose cuffs have hyperbolic length uniformly bounded above, which may be of independent interest. 

   more » « less
3. Composition of nested embeddings with an application to outlier removal

   Chawla, Shuchi; Sheridan, Kristin (January 2024, SIAM)

   We study the design of embeddings into Euclidean space with outliers. Given a metric space (X, d) and aninteger k, the goal is to embed all but k points in X (called the “outliers”) into ℓ2 with the smallest possibledistortion c. Finding the optimal distortion c for a given outlier set size k, or alternately the smallest k fora given target distortion c are both NP-hard problems. In fact, it is UGC-hard to approximate k to withina factor smaller than 2 even when the metric sans outliers is isometrically embeddable into ℓ2. We considerbi-criteria approximations. Our main result is a polynomial time algorithm that approximates the outlier setsize to within an O(log2 k) factor and the distortion to within a constant factor.The main technical component in our result is an approach for constructing Lipschitz extensions ofembeddings into Banach spaces (such as ℓp spaces). We consider a stronger version of Lipschitz extensionthat we call a nested composition of embeddings: given a low distortion embedding of a subset S of the metricspace X, our goal is to extend this embedding to all of X such that the distortion over S is preserved, whereasthe distortion over the remaining pairs of points in X is bounded by a function of the size of X \ S. Priorwork on Lipschitz extension considers settings where the size of X is potentially much larger than that of Sand the expansion bounds depend on |S|. In our setting, the set S is nearly all of X and the remaining setX \ S, a.k.a. the outliers, is small. We achieve an expansion bound that is polylogarithmic in |X \ S|. 

   more » « less
4. Computing β-Stretch Paths in Drawings of Graphs

   Arkin, E; Darabi, F; Efrat, A; Frank, F; Fulek, R; Kobourov, S; Mitchell, J (October 2020, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT))

   Let f be a drawing in the Euclidean plane of a graph G, which is understood to be a 1-dimensional simplicial complex. We assume that every edge of G is drawn by f as a curve of constant algebraic complexity, and the ratio of the length of the longest simple path to the the length of the shortest edge is poly(n). In the drawing f, a path P of G, or its image in the drawing π = f(P), is β-stretch if π is a simple (non-self-intersecting) curve, and for every pair of distinct points p ∈ P and q ∈ P , the length of the sub-curve of π connecting f(p) with f(q) is at most β∥f(p) − f(q)∥, where ∥.∥ denotes the Euclidean distance. We introduce and study the β-stretch Path Problem (βSP for short), in which we are given a pair of vertices s and t of G, and we are to decide whether in the given drawing of G there exists a β-stretch path P connecting s and t. We also output P if it exists. The βSP quantifies a notion of “near straightness” for paths in a graph G, motivated by gerrymandering regions in a map, where edges of G represent natural geographical/political boundaries that may be chosen to bound election districts. The notion of a β-stretch path naturally extends to cycles, and the extension gives a measure of how gerrymandered a district is. Furthermore, we show that the extension is closely related to several studied measures of local fatness of geometric shapes. We prove that βSP is strongly NP-complete. We complement this result by giving a quasi-polynomial time algorithm, that for a given ε > 0, β ∈ O(poly(log |V (G)|)), and s, t ∈ V (G), outputs a β-stretch path between s and t, if a (1 − ε)β-stretch path between s and t exists in the drawing. 

   more » « less
5. Square Packings and Rectifiable Doubling Measures

   Badger, Matthew; Schul, Raanan (May 2025, Discrete analysis)

   We prove that for all integers 2≤m≤d−1, there exists doubling measures on ℝd with full support that are m-rectifiable and purely (m−1)-unrectifiable in the sense of Federer (i.e. without assuming μ≪m). The corresponding result for 1-rectifiable measures is originally due to Garnett, Killip, and Schul (2010). Our construction of higher-dimensional Lipschitz images is informed by a simple observation about square packing in the plane: N axis-parallel squares of side length s pack inside of a square of side length ⌈N1/2⌉s. The approach is robust and when combined with standard metric geometry techniques allows for constructions in complete Ahlfors regular metric spaces. One consequence of the main theorem is that for each m∈{2,3,4} and s0, f(E) has Hausdorff dimension s, and μ(f(E))>0. This is striking, because m(f(E))=0 for every Lipschitz map f:E⊂ℝm→ℍ1 by a theorem of Ambrosio and Kirchheim (2000). Another application of the square packing construction is that every compact metric space 𝕏 of Assouad dimension strictly less than m is a Lipschitz image of a compact set E⊂[0,1]m. Of independent interest, we record the existence of doubling measures on complete Ahlfors regular metric spaces with prescribed lower and upper Hausdorff and packing dimensions. 

   more » « less