Truly Optimal Euclidean Spanners
Hung Le, Shay Solomon · 2019
Euclidean spanners are important geometric structures, having found numerous applications over the years. Cornerstone results in this area from the late 80s and early 90s state that for any d-dimensional n-point Euclidean space, there exists a (1+ε) -spanner with O(nε^-d+1) edges and lightness (normalized weight) O(ε^-2d)^1. Surprisingly, the fundamental question of whether or not these dependencies on ε and d for small d can be improved has remained elusive, even for d = 2. This question naturally arises in any application of Euclidean spanners where precision is a necessity (thus ε is tiny). In the most extreme case ε is inverse polynomial in n, and then one could potentially improve the size and lightness bounds by factors that are polynomial in n. The state-of-the-art bounds O(nε^-d+1) and O(ε^-2d) on the size and lightness of spanners are realized by the greedy spanner. In 2016, Filtser and Solomon [25] proved that, in low dimensional spaces, the greedy spanner is “near-optimal''; informally, their result states that the greedy spanner for dimension d is just as sparse and light as any other spanner but for dimension larger by a constant factor. Hence the question of whether the greedy spanner is truly optimal remained open to date. The contribution of this paper is two-fold. 1) We resolve these longstanding questions by nailing down the exact dependencies on ε and d and showing that the greedy spanner is truly optimal. Specifically, for any d= O(1), ε = Ω(n^-1/d-1): • We show that any (1+ε) -spanner must have Ω(nε^-d+1) edges, implying that the greedy (and other) spanners achieve the optimal size. • We show that any (1+ε) -spanner must have lightness Ω(ε^-d), and then improve the upper bound on the lightness of the greedy spanner from O(ε^-2d) to Õ_ε (ε^-d). 2) We then complement our negative result for the size of spanners with a rather counterintuitive positive result: Steiner points lead to a quadratic improvement in the size of spanners! Our bound for the size of Steiner spanners is tight as well (up to lower-order terms).