摘要：Spanners for low dimensional spaces (e.g. Euclidean space of constant dimension, or doubling metrics) are well understood. This lies in contrast to the situation in high dimensional spaces, where except for the work of Har-Peled, Indyk and Sidiropoulos (SODA 2013), who showed that any n-point Euclidean metric has an O(t)-spanner with O~(n^{1+1/t^2}) edges, little is known.
In this paper we study several aspects of spanners in high dimensional normed spaces. First, we build spanners for finite subsets of l_p with 1
关键词：Spanners; Stochastic Decompositions; High Dimensional Euclidean Space; Doubling Dimension; Genus Graphs
