TY - GEN
T1 - Euclidean spanners in high dimensions
AU - Har-Peled, Sariel
AU - Indyk, Piotr
AU - Sidiropoulos, Anastasios
PY - 2013
Y1 - 2013
N2 - A classical result in metric geometry asserts that any n-point metric admits a linear-size spanner of dilation O(log n) [PS89]. 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 Erdo{combining double acute accent}s [Erd63]. 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(√log n). Using the LSH scheme of Andoni and Indyk [AI06] we further show that for any c > 1, there exist spanners of size roughly O(n 1+1/c2) and dilation O(c). Finally, we also exhibit super-linear lower bounds on the size of spanners with constant dilation.
AB - A classical result in metric geometry asserts that any n-point metric admits a linear-size spanner of dilation O(log n) [PS89]. 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 Erdo{combining double acute accent}s [Erd63]. 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(√log n). Using the LSH scheme of Andoni and Indyk [AI06] we further show that for any c > 1, there exist spanners of size roughly O(n 1+1/c2) and dilation O(c). Finally, we also exhibit super-linear lower bounds on the size of spanners with constant dilation.
UR - http://www.scopus.com/inward/record.url?scp=84876019022&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84876019022&partnerID=8YFLogxK
U2 - 10.1137/1.9781611973105.57
DO - 10.1137/1.9781611973105.57
M3 - Conference contribution
AN - SCOPUS:84876019022
SN - 9781611972511
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 804
EP - 809
BT - Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013
PB - Association for Computing Machinery
T2 - 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013
Y2 - 6 January 2013 through 8 January 2013
ER -