Analyst's traveling salesman theorem

From Wikipedia, the free encyclopedia
Jump to: navigation, search

The analyst's traveling salesman problem is an analog of the traveling salesman problem in combinatorial optimization. In its simplest and original form, it asks under what conditions may a set E in two-dimensional Euclidean space \mathbb{R}^2 be contained inside a rectifiable curve of finite length. So while in the original traveling salesman problem, one asks for the shortest way to visit every vertex in a graph with a discrete path, this analytical version requires the curve to visit perhaps infinitely many points.

β-numbers[edit]

A posteriori, for E to be contained in a rectifiable curve Γ, since Γ has tangents at H1-almost every point in Γ (where H1 denotes one-dimensional Hausdorff measure), E must look flat when you zoom in on points in E. This suggests that a condition that would tell us whether a set could be contained in a curve must somehow incorporate information about how flat E is when we zoom in on points of E at different scales.

This discussion motivates the definition of the following quantity:

\beta_{E}(Q)=\frac{1}{\ell(Q)}\inf\{\delta:\text{ there is a line }L\text{ so that for every }x\in E\cap Q, \; \text{dist}(x,L)<\delta\},

Where Q is any square, \ell(Q) is the sidelength of Q, and dist(xL) measures the distance from x to the line L. Intuitively, 2\beta_E(Q)\ell(Q) is the width of the smallest rectangle containing the portion of E inside Q, and hence \beta_E(Q) gives us a scale invariant notion of flatness.

Jones' traveling salesman theorem in R2[edit]

Let Δ denote the collection of dyadic squares, that is,

\Delta=\{[i2^{k},(i+1)2^{k}]\times[j2^{k},(j+1)2^{k}]: i,j,k\in\mathbb{Z}\},

where \mathbb{Z} denotes the set of integers. For a set E\subseteq\mathbb{R}^2, define

\beta(E)=\text{diam} E+ \sum_{Q\in\Delta}\beta_{E}(3Q)^2 \ell(Q)

where diam E is the diameter of E. Then Peter Jones'[1] analyst's traveling salesman theorem may be stated as follows:

  • There is a number C > 0 such that whenever E is a set with such that β(E) < ∞, E can be contained in a curve with length no more than (E).
  • Conversely (and substantially more difficult to prove), if Γ is a rectifiable curve, then β(Γ) < CH1(Γ).

Generalizations and Menger curvature[edit]

Euclidean space and Hilbert space[edit]

  • The Traveling Salesman Theorem was shown to hold in general Euclidean spaces by Kate Okikiolu,[2] that is, the same theorem above holds for sets E\subseteq\mathbb{R}^d, d > 1, where Δ is now the collection of dyadic cubes in \mathbb{R}^d defined in a similar way as dyadic squares. In her proof, the constant C grows exponentially with the dimension d.
  • With some slight modifications to the definition of β(E), Raanan Schul[3] showed Traveling Salesman Theorem also holds for sets E that lie in any Hilbert Space, and in particular, implies the theorems of Jones and Okikiolu, where now the constant C is independent of dimension. (In particular, this involves using β-numbers of balls instead of cubes).

Menger curvature and metric spaces[edit]

  • Hahlomaa[4] further adjusted the definition of β(E) to get a condition for when a set E of an arbitrary metric space may be contained in the Lipschitz-image of a subset A\subseteq\mathbb{R} of positive measure. For this, he had to redefine the definition of the β-numbers using menger curvature (since in a metric space there isn't necessarily a notion of a cube or a straight line).
  • Menger curvature, as in the previous example, can be used to give numerical estimates that determine whether a set contains a rectifiable subset, and the proofs of these results frequently depend on β-numbers.

References[edit]

  1. ^ Jones, Peter (1990). "Rectifiable sets and the Traveling Salesman Problem". Inventiones Mathematicae 102: 1–15. doi:10.1007/BF01233418. 
  2. ^ Okikiolu, Kate (1992). "Characterization of subsets of rectifiable curves in Rn". Journal of the London Mathematical Society 46: 336–348. doi:10.1112/jlms/s2-46.2.336. 
  3. ^ Schul, Raanan (2007). "Subsets of Rectifiable curves in Hilbert Space—The Analyst's TSP". Journal d'Analyse Mathématique 103: 331–375. doi:10.1007/s11854-008-0011-y. 
  4. ^ Hahlomaa, Immo (2005). "Menger curvature and Lipschitz parametrizations in metric spaces". Fund. Math. 185: 143–169. doi:10.4064/fm185-2-3.