2026-08-25T17:34:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27188 2026-08-25T13:18:17Z ddc:004 open_access

A Dynamic (1+ε)-Spanner for Disk Intersection Graphs de Berg, Sarita van der Hoog, Ivor Rotenberg, Eva Vistisen, Johanne Müller Wong, Sampson intersection graphs dynamic data structures spanners 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(ε^{-2} n log⁴n log Ψ) space and has an O((Ψ/ε)² log⁴n log²Ψ log²(ε^{-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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sarita de Berg and Ivor van der Hoog and Eva Rotenberg and Johanne Müller Vistisen and Sampson Wong 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.52 urn:nbn:de:0030-drops-271880 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.52 eng https://creativecommons.org/licenses/by/4.0/legalcode