Home Bookmarks Papers Blog

Euclidean Spanners in High Dimensions

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(n1+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(n1+1/c^2) and dilation O(c). Finally, we also exhibit super-linear lower bounds on the size of spanners with constant dilation.

Last modified: Tue Jul 9 11:26:42 CDT 2013