How to take shortcuts in Euclidean space: making a given set into a short quasi-convex set

DOI10.1112/PLMS/PDS005zbMATH Open1250.28001arXiv0912.1356OpenAlexW2029529119MaRDI QIDQ2909058FDOQ2909058

Authors: Jonas Azzam, Raanan Schul 

Publication date: 29 August 2012

Published in: Proceedings of the London Mathematical Society. Third Series (Search for Journal in Brave)

Abstract: For a given connected set $Gamma$ in $d-$dimensional Euclidean space, we construct a connected set $ildeGammasupsetGamma$ such that the two sets have comparable Hausdorff length, and the set $ildeGamma$ has the property that it is quasiconvex, i.e. any two points $x$ and $y$ in $ildeGamma$ can be connected via a path, all of which is in $ildeGamma$, which has length bounded by a fixed constant multiple of the Euclidean distance between $x$ and $y$. Thus, for any set $K$ in $d-$dimensional Euclidean space we have a set $ildeGamma$ as above such that $ildeGamma$ has comparable Hausdorff length to a shortest connected set containing $K$. Constants appearing here depend only on the ambient dimension $d$. In the case where $Gamma$ is Reifenberg flat, our constants are also independent the dimension $d$, and in this case, our theorem holds for $Gamma$ in an infinite dimensional Hilbert space. This work closely related to $k-$spanners, which appear in computer science. Keywords: chord-arc, quasiconvex, k-spanner, traveling salesman.

Full work available at URL: https://arxiv.org/abs/0912.1356

Recommendations

• scientific article; zbMATH DE number 5245088
• How to take short cuts
• Shortcut sets for plane Euclidean networks (extended abstract)
• Subsets of rectifiable curves in Hilbert space-the analyst's TSP
• Sets admitting connection by graphs of finite length

zbMATH Keywords

traveling salesman problemquasi-convexity1-dimensional Haussdorff measure

Mathematics Subject Classification ID

Convexity of real functions of several variables, generalizations (26B25) Length, area, volume, other geometric measure theory (28A75)

Cited In (4)

• Hölder curves and parameterizations in the Analyst's traveling salesman theorem
• Subsets of rectifiable curves in Banach spaces. I: Sharp exponents in traveling salesman theorems
• An upper bound for the length of a traveling salesman path in the Heisenberg group
• Tree-like decompositions of simply connected domains

This page was built for publication: How to take shortcuts in Euclidean space: making a given set into a short quasi-convex set

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2909058)