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 and acknowledge you have read our privacy policy.