Sparse Bounded Hop-Spanners for Geometric Intersection Graphs

Abstract

We present new results on $2$- and $3$-hop spanners for geometric intersection graphs. These include improved upper and lower bounds for $2$- and $3$-hop spanners for many geometric intersection graphs in ${\mathbb{R}}^d$. For example, we show that the intersection graph of $n$ balls in ${\mathbb{R}}^d$ admits a $2$-hop spanner of size $O^{\ast }\left(n^{\frac{3}{2}-\frac{1}{2(2\lfloor d/2\rfloor +1)}}\right)$ and the intersection graph of $n$ fat axis-parallel boxes in ${\mathbb{R}}^d$ admits a $2$-hop spanner of size $O(n{\log }^{d+1}n)$. Furthermore, we show that the intersection graph of general semi-algebraic objects in ${\mathbb{R}}^d$ admits a $3$-hop spanner of size $O^{\ast }\left(n^{\frac{3}{2}-\frac{1}{2(2D-1)}}\right)$, where $D$ is a parameter associated with the description complexity of the objects. For such families (or more specifically, for tetrahedra in ${\mathbb{R}}^3$), we provide a lower bound of $\hat{I}\text{c◯}(n^{\frac{4}{3}})$. For $3$-hop and axis-parallel boxes in ${\mathbb{R}}^d$, we provide the upper bound $O(n{\log }^{d-1}n)$ and lower bound $\hat{I}\text{c◯}\left(n(\frac{\log n}{\log \log n}{)}^{d-2}\right)$.

21 pages. An extended abstract of this paper will appear in the Proceedings of SoCG 2025