A Dynamic (1+ε)-Spanner for Disk Intersection Graphs

We maintain a (1 + ε)-spanner over the disk intersection graph of a dynamic set of disks. We restrict all disks to have their diameter in [4, Ψ] for some fixed and known Ψ. The resulting (1 + ε)-spanner has size O(nε−2 log Ψ log(ε−1)), where n is the present number of disks. We develop a novel use of persistent data structures to dynamically maintain our (1 + ε)-spanner. Our approach requires O(ε−2n log4 n log Ψ) space and has an O(( Ψ/ε )2 log4 n log2 Ψ log2(ε−1)) expected amortised update time. For constant ε and Ψ, this spanner has near-linear size, uses near-linear space and has polylogarithmic update time. Furthermore, we observe that for any ε < 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 Ψ by a polylogarithmic dependency. Finally, we generalise our results to d-dimensional hypercubes.