An optimal-time construction of sparse Euclidean spanners with tiny diameter
Shay Solomon · 2011
In STOC’95 [5] Arya et al. showed that for any set of n points in Rd, a (1 + ǫ)-spanner with diameter at most 2 (respectively, 3) and O(nlog n) edges (resp., O(nlog log n) edges) can be built in O(nlog n) time. Moreover, Arya et al. [5] conjectured that one can build in O(nlog n) time a (1+ǫ)-spanner with diameter at most 4 and O(nlog ∗ n) edges. Since then, this conjecture became a central open problem in this area. Nevertheless, very little progress on this problem was reported up to this date. In particular, the previous state-of-the-art subquadratic-time construction of (1 + ǫ)-spanners with o(nlog log n) edges due to Arya et al. [5] produces spanners with diameter 8. In addition, general tradeoffs between the diameter and number of edges were established [5, 26]. Specifically, it was shown in [5, 26] that for any k ≥ 4, one can build in O(n(log n)2kαk(n)) time a (1+ǫ)-spanner with diameter at most 2k and O(n2kαk(n)) edges. The function αk is the inverse of a certain Ackermann-style function at the ⌊k/2⌋th level of the primitive recursive hierarchy, where α0(n) = ⌈n/2⌉,α1(n) = ⌈ √ n ⌉,α2(n) = ⌈log n⌉,α3(n) = ⌈log log n⌉,α4(n) = log ∗ n,α5(n) = ⌊1 2 log ∗ n⌋,..., etc. It is also known [26] that if one allows quadratic time then these bounds can be improved. Specifically, for any k ≥ 4, a (1 + ǫ)-spanner with diameter at most k and O(nkαk(n)) edges can be constructed in O(n2) time [26]. A major open question in this area is whether one can construct within time O(nlog n+nkαk(n)) a (1+ǫ)-spanner with diameter at most k and O(nkαk(n)) edges. This question in the particular case of k = 4 coincides with the aforementioned conjecture of Arya et al. [5]. In this paper we answer this long-standing question in the affirmative. Moreover, in fact, we provide a stronger result. Specifically, we show that for any k ≥ 4, a (1 + ǫ)-spanner with diameter at most k and O(nαk(n)) edges can be built in optimal time