Improved approximation schemes for geometrical graphs via ``spanners'' and ``banyans'' Satish B. Rao \& Warren D. Smith Abstract We give deterministic and randomized algorithms to find a Euclidean traveling salesman tour (TST) of length within $(1+1/s)$ times optimal. They run in $O(N \log N)$ time and $O(N)$ space for constant dimension and $s$. These time and space bounds are optimal in an algebraic computation tree model. We can also find a $(1+1/s)$ times optimal length 2-matching (M2M), edge cover (EC), minimum spanning tree (MST), Steiner minimal tree (SMT), rectilinear ditto (RSMT), and related graphs in the same time bound. This improves recent algorithms of Arora, which had used $N (\log N)^{O(s^{d-1})}$ time in fixed dimension $d$ to produce a $(1+1/s)$ times optimal TST (or SMT, RSMT) with success probability $1/2$. To verify success, however, Arora could only use a deterministic version of his algorithm that took a factor of $N^d$ more time. The increase in running time for our deterministic version depends only on $s$. Arora's approach can also be extended to produce other $(1+\epsilon)$-approximate geometrical graphs besides TSTs, e.g. the minimum matching (MM) and subgraph versions of the MST and TST problems. Our methods (at least at the moment) don't apply to those problems, but we can produce a $1.001 \exp ( 8 \cdot 2^{1-1/(d-1)} \sqrt{d} )$-approximate MM in $O(N \log N)$ Monte Carlo time. Our algorithms are based on using low-weight Euclidean {\em spanner graphs} (and generalizations of them) in conjunction with the hierarchical structure theorems that serve as the basis of Arora's work. A ``$t$-spanner'' is a graph on $N$ sites such that shortest path distance between two spanner vertices approximates the Euclidean distance to within a factor of $t$. By making work by Arya, Das, et al. more explicit, we show that a $(1+1/s)$-spanner of $N$ sites in $d$-space is computable in $(sd)^{O(d)} N \log N$ time and $(sd)^{O(d)} N$ space, has maximum valence $(sd)^{O(d)}$, and is $(sd)^{O(d)}$ times longer than the MST. We show that spanners can in principle be made orders of magnitude shorter and simpler by allowing ``Steiner points.'' We introduce a remarkable generalization of the notion of ``$t$-spanner,'' the ``$t$-banyan,'' that $t$-approximates interconnection costs for site subsets of {\it any} cardinality, not just 2. If $d \ge 1$ and $\epsilon > 0$ are fixed, we show a $(1+\epsilon)$-banyan of $N$ sites in $d$-space exists, has $O(N)$ vertices and $O(N)$ edges, is only a constant factor longer than the MST, and is computable in $O(N \log N)$ time. Keywords Polynomial time approximation schemes, optimal algorithms, derandomization, Traveling salesman tour, Steiner minimum tree, Minimum spanning tree, Minimum matchings, 2-matchings, Edge cover, Rectilinear Steiner minimum tree, quadtrees, spanners, banyans. 4 figures 0 tables