Sariel Har-Peled,
Piotr Indyk,
and Anastasios Sidiropoulos.

A classical result in metric geometry asserts that any n-point
metric admits a linear-size spanner of dilation O( log n)
[ps-gs-89]. More generally, for any c>1, any metric
space admits a spanner of size O(n^{1+1/c}), and
dilation at most c. This bound is tight assuming the well-known
girth conjecture of Erdos [e-epgt-63] .

We show that for a metric induced by a set of n points in
high-dimensional Euclidean space, it is possible to obtain improved
dilation/size trade-offs. More specifically, we show that any
n-point Euclidean metric admits a near-linear size spanner of
dilation O(\sqrt log n). Using the \LSH scheme of Andoni and
Indyk [ai-nohaa-06] we further show that for any c>1, there
exist spanners of size roughly O(n^{1+1/c^2}) and
dilation O(c). Finally, we also exhibit super-linear lower
bounds on the size of spanners with constant dilation.