DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2026.52

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

Authors: Sarita de Berg, Ivor van der Hoog, Eva Rotenberg, Johanne Müller Vistisen, and Sampson Wong

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

Abstract

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.

Cite as

Sarita de Berg, Ivor van der Hoog, Eva Rotenberg, Johanne Müller Vistisen, and Sampson Wong. A Dynamic (1+ε)-Spanner for Disk Intersection Graphs. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 52:1-52:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{deberg_et_al:LIPIcs.ESA.2026.52,
  author =	{de Berg, Sarita and van der Hoog, Ivor and Rotenberg, Eva and Vistisen, Johanne M\"{u}ller and Wong, Sampson},
  title =	{{A Dynamic (1+\epsilon)-Spanner for Disk Intersection Graphs}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{52:1--52:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.52},
  URN =		{urn:nbn:de:0030-drops-271880},
  doi =		{10.4230/LIPIcs.ESA.2026.52},
  annote =	{Keywords: intersection graphs, dynamic data structures, spanners}
}

Search Results

Documents authored by Vistisen, Johanne Müller

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

Abstract

Cite as

Thanks for your feedback!

Could not send message