arXiv preprint ·
Bourgain's Theorem for a Union of Euclidean Metric Spaces
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We study the distortion of embedding a union of $k$ Euclidean sets into Euclidean space. We show that a union of $k$ Euclidean sets can be embedded with distortion at most $O(k^{1.128} \log k)$, independent of the number of points. This is an exponential improvement over the previous best known upper bound of $2^{O(k)}$ obtained by iterating the result of Makarychev and Makarychev (2016) for the special case $k = 2$. Surprisingly, with the additional assumption that each Euclidean set remains Euclidean when we adjoin any other two points, we can obtain an asymptotically tight distortion of $O(\log k)$, thus, providing a generalization of Bourgain's Theorem (1985). Along the way, we also show that the distortion of the union can be upper bounded by $O(\log k)$ times the maximum of the Lipschitz extension constants of individual Euclidean sets.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Diameter bounds for complexes that are close to flag or close to normal
Sharp isoperimetry in groups of polynomial growth
Multiscale Closing Index (MCI) for measuring structural similarity between 2D point sets
Levenshtein-type bounds for $(a,b)$-avoiding spherical codes
A generalization of the Gauss Lemma
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.