Sparse Euclidean Spanners with Tiny Diameter
Shay Solomon · ACM Transactions on Algorithms · 2013
In STOC’95, Arya et al. [1995] showed that for any set of n points in R d , a (1 + ε )-spanner with diameter at most 2 (respectively, 3) and O ( n log n ) edges (respectively, O ( n log log n ) edges) can be built in O ( n log n ) time. Moreover, it was shown in Arya et al. [1995] and Narasimhan and Smid [2007] that for any k ≥ 4, one can build in O ( n (log n )2 k α k ( n )) time a (1 + ε )-spanner with diameter at most 2 k and O ( n 2 k α k ( n )) edges. The function α k is the inverse of a certain 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 ) = 12 log* n , ..., etc. It is also known [Narasimhan and Smid 2007] 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 ( n 2 ) time [Narasimhan and Smid 2007]. A major open question in this area is whether one can construct within time O ( n log n + nkα k ( n )) a (1 + ε )-spanner with diameter at most k and O ( nkα k ( n )) edges. In this article, we answer this 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 O ( n log n ).