A dynamic $(1+\epsilon )$-spanner for disk intersection graphs

Abstract

We maintain a $(1+\epsilon )$-spanner over the disk intersection graph of a dynamic set of disks. We restrict all disks to have their diameter in $[4,\hat{I}¨]$ for some fixed and known $\hat{I}¨$. The resulting $(1+\epsilon )$-spanner has size $O(n{\epsilon }^{-2}\log \hat{I}¨\log ({\epsilon }^{-1}))$, where $n$ is the present number of disks. We develop a novel use of persistent data structures to dynamically maintain our $(1+\epsilon )$-spanner. Our approach requires $O({\epsilon }^{-2}n{\log }^{4}n\log \hat{I}¨)$ space and has an $O({\left(\frac{\hat{I}}{¨}\epsilon \right)}^2{\log }^{4}n{\log }^2\hat{I}¨{\log }^2({\epsilon }^{-1}))$ expected amortised update time. For constant $\epsilon$ and $\hat{I}¨$, this spanner has near-linear size, uses near-linear space and has polylogarithmic update time. Furthermore, we observe that for any $\epsilon <1$, our spanner also serves as a connectivity data structure. With a slight adaptation of our techniques, this leads to better bounds for dynamically supporting connectivity queries in a disk intersection graph. In particular, we improve the space usage when compared to the dynamic data structure of (Baumann et al., DCG'24), replacing the linear dependency on $\hat{I}¨$ by a polylogarithmic dependency. Finally, we generalise our results to $d$-dimensional hypercubes.

To appear at ESA 2026