Optimal Bounds for Spanners and Tree Covers in Doubling Metrics

An La, Hung Le, Shay Solomon +4

It is known that any $n$-point set in the $d$-dimensional Euclidean space ${\mathbb{R}}^d$, for $d=O(1)$, admits: 1) a $(1+\hat{I}\mu )$-spanner with maximum degree $\tilde{O}(\hat{I}{\mu }^{-d+1})$ a…