2010/05/22 by Shay Solomon, Solomon, Shay
Computer Science · #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.CG #cs.DS
paper · pdf · doi:10.48550/arxiv.1005.4155
28 pages, 3 figures
arxiv created 2010/05/22 · arxiv updated 2011/08/31
In STOC'95 \citeADMSS95 Arya et al. showed that for any set of n points in \mathbb Rd, a (1+ε)-spanner with diameter at most 2 (respectively, 3) and O(n log n) edges (resp., O(n log log n) edges) can be built in O(n log n) time. Moreover, it was shown in \citeADMSS95,NS07 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(n 2k αk(n)) edges. The function αk is the inverse of a certain function at the \lfloor k/2 \rfloorth level of the primitive recursive hierarchy, where α0(n) = \lceil n/2 \rceil, α1(n) = \lceil √(n) \rceil, α2(n) = \lceil logn \rceil, α3(n) = \lceil loglogn \rceil, α4(n) = log^* n, …, etc. It is also known \citeNS07 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(n k αk(n)) edges can be constructed in O(n2) time \citeNS07. A major open problem in this area is whether one can construct within time O(n log n + n k αk(n)) a (1+ε)-spanner with diameter at most k and O(n k αk(n)) edges. In this paper 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). The tradeoff between the diameter and number of edges of our spanners is tight up to constant factors in the entire range of parameters.