It is well-known that Euclidean space of dimension $d$ has a $(1+\epsilon)$-spanner of weight at most $\epsilon^{-O(d)}\cdot w(MST)$ (see Chapter 14 of Geometric Spanner Network book by Narashimhan and Smid).

However, I can not find any reference on the lower bound, that showes there is a set of points in dimension $d$ Euclidean space whose $(1+\epsilon)$-spanner has weight at least $\epsilon^{-\Omega(d)}\cdot w(MST)$. Is this a folklore result?

A point set that I came up with that satisfies the lower bound is a uniform point set in a unit ball where the pairwise distance is at least $2\epsilon$. This point set only has $\epsilon^{-O(d)}$ points, but we can have many unit balls arranged in a path-like fashion to get a bigger point set.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.