{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreier3hsvk7znjtmqnbeg3mxx5ujr3g4wlwagcozeuun6tro26kazky",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mkmeerf7ywr2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2604.25397v1",
  "publishedAt": "2026-04-29T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Sarita de Berg",
    "Ivor van der Hoog",
    "Eva Rotenberg",
    "Johanne M. Vistisen",
    "Sampson Wong"
  ],
  "textContent": "**Authors:** Sarita de Berg, Ivor van der Hoog, Eva Rotenberg, Johanne M. Vistisen, Sampson Wong\n\nWe maintain a $(1+\\varepsilon)$-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+\\varepsilon)$-spanner has size $O(n \\varepsilon^{-2} \\log Ψ\\log (\\varepsilon^{-1}))$, where $n$ is the present number of disks. We develop a novel use of persistent data structures to dynamically maintain our $(1+\\varepsilon)$-spanner. Our approach requires $O(\\varepsilon^{-2} n \\log^4 n \\log Ψ)$ space and has an $O( \\left( \\fracΨ{\\varepsilon} \\right)^2 \\log^4 n \\log^2 Ψ\\log^2 (\\varepsilon^{-1}))$ expected amortised update time. For constant $\\varepsilon$ and $Ψ$, this spanner has near-linear size, uses near-linear space and has polylogarithmic update time. Furthermore, we observe that for any $\\varepsilon < 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.",
  "title": "A dynamic $(1+\\varepsilon)$-spanner for disk intersection graphs"
}