Sub-quadratic (1+\eps)-approximate Euclidean Spanners, with Applications

Alexandr Andoni, Hengjie Zhang

We study graph spanners for point-set in the high-dimensional Euclidean space. On the one hand, we prove that spanners with stretch <\sqrt{2} and subquadratic size are not possible…