Can't See the Forest for the Trees

Spanners for metric spaces have been extensively studied, perhaps most notably in low-dimensional Euclidean spaces - due to their numerous applications. Euclidean spanners can be viewed as means of compressing the (n2) pairwise distances of a d-dimensional Euclidean space into O(n) = O∈,d (n) spanner edges, so that the spanner distances preserve the original distances to within a factor of 1 + ε, for any ε > 0. Moreover, one can compute such spanners efficiently in the standard centralized and distributed settings. Once the spanner has been computed, it serves as a "proxy" overlay network, on which the computation can proceed, which gives rise to huge savings in space and other important quality measures. The original metric enables us to "navigate" optimally - a single