The traveling salesman problem and harmonic analysis (Q1174949)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The traveling salesman problem and harmonic analysis |
scientific article |
Statements
The traveling salesman problem and harmonic analysis (English)
0 references
25 June 1992
0 references
The author considers the following generalization of the classical traveling salesman problem: given a set \(K\) in the plane, is it possible to find the length of the shortest curve passing through \(K\)? For a dyadic square \(Q\) in the plane, the author defines the quantity \(\beta_ K(Q)=\inf_ L\sup_{z\in K\cap 3Q} l(Q)^{-1}\text{dist}(z,L)\), where the infimum is taken over all lines \(L\) in the plane; this gives a measure of the extent to which \(K\) deviates from lines on \(Q\). The quantity \(\beta^ 2(K)= \sum_ Q \beta^ 2_ K(Q)l(Q)\), where the sum is taken over all dyadic squares \(Q\), can be used to characterize the sets \(K\) which occur as subsets of a rectifiable curve, to wit: there exists a rectifiable curve \(\Gamma\) with \(K\subseteq \Gamma\) if and only if \(K\) is bounded and \(\beta^ 2(K)\) is finite. The main result of this paper is the following (Theorem 1): If \(\Gamma_ 0\) is the shortest curve containing \(K\), then there is a universal constant \(C_ 0\) such that, for all \(K\), \(C^{-1}_ 0\leq(\text{diam}(K)+ \beta^ 2(K))/l(\Gamma_ 0)\leq C_ 0\). The proof of this theorem makes use of geometric results about the extent to which a given simply connected domain may be approximated by Lipschitz domains. Various corollaries of Theorem 1 are discussed, concerning harmonic measure and the connection of these ideas with the Cauchy integral operator on Lipschitz curves.
0 references
traveling salesman problem
0 references
dyadic square
0 references
Lipschitz domains
0 references
harmonic measure
0 references
Cauchy integral operator on Lipschitz curves
0 references