Paper Info

Title | ||
---|---|---|

Euclidean spanners in high dimensions |

Abstract | ||
---|---|---|

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 Erdő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(@@@@) and dilation O(c). Finally, we also exhibit super-linear lower bounds on the size of spanners with constant dilation. |

Year | DOI | Venue |
---|---|---|

2013 | 10.5555/2627817.2627874 | SODA '13: ACM-SIAM Symposium on Discrete Algorithms
New Orleans
Louisiana
January, 2013 |

Keywords | DocType | ISBN |

algorithms,design,theory,graph theory,geometrical problems and computations | Conference | 978-1-61197-251-1 |

Citations | PageRank | References |

0 | 0.34 | 6 |

Authors | ||

3 |

Authors (3 rows)

Cited by (0 rows)

References (6 rows)

Name | Order | Citations | PageRank |
---|---|---|---|

Sariel Har-Peled | 1 | 2630 | 191.68 |

Piotr Indyk | 2 | 10925 | 918.34 |

Anastasios Sidiropoulos | 3 | 330 | 31.78 |