Abstract
In STOC'95 [S. Arya et al., 1995] Arya et al. showed that any set of n points in ℝ^d admits a (1+ε)spanner with hopdiameter at most 2 (respectively, 3) and O(n log n) edges (resp., O(n log log n) edges). They also gave a general upper bound tradeoff of hopdiameter k with O(n α_k(n)) edges, for any k ≥ 2. The function α_k is the inverse of a certain Ackermannstyle function, where α₀(n) = ⌈n/2⌉, α₁(n) = ⌈√n⌉, α₂(n) = ⌈log n⌉, α₃(n) = ⌈log log n⌉, α₄(n) = log^* n, α₅(n) = ⌊ 1/2 log^*n ⌋, …. Roughly speaking, for k ≥ 2 the function α_{k} is close to ⌊(k2)/2⌋iterated logstar function, i.e., log with ⌊(k2)/2⌋ stars.
Despite a large body of work on spanners of bounded hopdiameter, the fundamental question of whether this tradeoff between size and hopdiameter of Euclidean (1+ε)spanners is optimal has remained open, even in onedimensional spaces. Three lower bound tradeoffs are known:
 An optimal k versus Ω(n α_k(n)) by Alon and Schieber [N. Alon and B. Schieber, 1987], but it applies to stretch 1 (not 1+ε).
 A suboptimal k versus Ω(nα_{2k+6}(n)) by Chan and Gupta [H. T.H. Chan and A. Gupta, 2006].
 A suboptimal k versus Ω(n/(2^{6⌊k/2⌋}) α_k(n)) by Le et al. [Le et al., 2022]. This paper establishes the optimal k versus Ω(n α_k(n)) lower bound tradeoff for stretch 1+ε, for any ε > 0, and for any k. An important conceptual contribution of this work is in achieving optimality by shaving off an extremely slowly growing term, namely 2^{6⌊k/2⌋} for k ≤ O(α(n)); such a finegrained optimization (that achieves optimality) is very rare in the literature.
To shave off the 2^{6⌊k/2⌋} term from the previous bound of Le et al., our argument has to drill much deeper. In particular, we propose a new way of analyzing recurrences that involve inverseAckermann style functions, and our key technical contribution is in presenting the first explicit construction of concave versions of these functions. An important advantage of our approach over previous ones is its robustness: While all previous lower bounds are applicable only to restricted 1dimensional point sets, ours applies even to random point sets in constantdimensional spaces.
BibTeX  Entry
@InProceedings{le_et_al:LIPIcs.SoCG.2023.47,
author = {Le, Hung and Milenkovi\'{c}, Lazar and Solomon, Shay},
title = {{Sparse Euclidean Spanners with Optimal Diameter: A General and Robust Lower Bound via a Concave InverseAckermann Function}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {47:147:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772730},
ISSN = {18688969},
year = {2023},
volume = {258},
editor = {Chambers, Erin W. and Gudmundsson, Joachim},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17897},
URN = {urn:nbn:de:0030drops178976},
doi = {10.4230/LIPIcs.SoCG.2023.47},
annote = {Keywords: Euclidean spanners, Ackermann functions, convex functions, hopdiameter}
}
Keywords: 

Euclidean spanners, Ackermann functions, convex functions, hopdiameter 
Collection: 

39th International Symposium on Computational Geometry (SoCG 2023) 
Issue Date: 

2023 
Date of publication: 

09.06.2023 