Euclidean spanners in high dimensions

Sariel Har-Peled, Piotr Indyk, Anastasios Sidiropoulos

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 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.

Original languageEnglish (US)
Title of host publicationProceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013
PublisherAssociation for Computing Machinery
Pages804-809
Number of pages6
ISBN (Print)9781611972511
DOIs
StatePublished - 2013
Event24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013 - New Orleans, LA, United States
Duration: Jan 6 2013Jan 8 2013

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013
Country/TerritoryUnited States
CityNew Orleans, LA
Period1/6/131/8/13

ASJC Scopus subject areas

  • Software
  • General Mathematics

Fingerprint

Dive into the research topics of 'Euclidean spanners in high dimensions'. Together they form a unique fingerprint.

Cite this