A dynamic (1 + ε)-spanner for disk intersection graphs

Q: What problem does the paper address for disk intersection graphs?

It maintains a (1+ε)-spanner over the disk intersection graph of a dynamic set of disks, while also deriving implications for connectivity queries.

Q: How is the disk set restricted in the spanner construction?

All disks are restricted to have their diameters within a fixed and known range [4, Ψ].

Q: What are the main size and update-time guarantees of the dynamic spanner?

The (1+ε)-spanner has size O(nε−2 log Ψ log(ε−1)). Using persistent data structures, it requires O(ε−2n log4 n log Ψ) space and achieves an expected amortised update time of O((Ψ/ε)^2 log4 n log2 Ψ log2(ε−1)).

Jul 16, 2026

Upload by Lucas Martin

Maintaining an approximately distance-preserving sparse subgraph is addressed for disk intersection graphs under dynamic disk updates. All disks are restricted to diameters within a known interval [4, Ψ]. The work constructs a (1 + ε)-spanner whose size is O(nε−2 log Ψ log(ε−1)) and maintains it via persistent data structures. It uses O(ε−2n log4 n log Ψ) space with expected amortised update time O((Ψ/ε)^2 log4 n log2 Ψ log2(ε−1)). For ε<1, the spanner also supports connectivity, improving dynamic connectivity bounds and extending results to d-dimensional hypercubes.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages39

Reading Time1 h 38 min

Introduction

Geometric spanners

Spanners in disk graphs

Dynamic connectivity in disk graphs

arXiv :2604 .25397v2 [ cs .CG] 10 Jul 2026 A dynamic (1 + ε)-spanner for disk intersection graphs Sarita de Berg \# IT University of Copenhagen, Denmark Ivor van der Hoog \# IT University of Copenhagen, Denmark Eva Rotenberg \# IT University of Copenhagen, Denmark Johanne Müller Vistisen \# IT University of Copenhagen, Denmark Sampson Wong \# University of Copenhagen, Denmark ~~ 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(ε−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. 2012 ACM Subject Classification Theory of computation → Computational geometry Keywords and phrases intersection graphs, dynamic data structures, spanners Funding This research was supported by Danmarks Frie Forskningsfond Case no. 10.46540/3160- 00020B, the VILLUM Foundation grant (VIL37507) “Efficient Recomputations for Changeful Problems”, and the European Union’s Marie Skłodowska-Curie Actions Postdoctoral Fellowship Project number No. 101146276. 2 A dynamic (1 + ε)-spanner for disk intersection graphs 1 Introduction Given a set of n geometric shapes, e.g. disks, the corresponding intersection graph has the shapes as its vertex set, and an edge between two shapes whenever they intersect (see Figure 1) . Disk intersection graphs are often used as a model for wireless ad-hoc networks [14,29,33], in particular, the radius of a disk equals the transmission range of the device. One of the central algorithmic challenges of disk intersection graphs is that, with n vertices, the graph may have Ω(n2 ) edges. Nonetheless, there are many problems that can be solved in subquadratic time in disk graphs [5,9,25,27,42,43,47] . Both weighted [5,23,32,34] and unweighted [9,11,13,47] disk intersection graphs have been studied; we will consider weighted disk intersection graphs where the weight of an edge is the Euclidean distance between the centres of the disks. We study two dynamic problems: maintaining a spanner for the disk intersection graph or a data structure for connectivity queries (for the latter, the edge weights are irrelevant) . Geometric spanners. Given a graph, a spanner is a subgraph that approximately preserves the distances of the original graph. Formally, a (1+ε)-spanner for a graph G is a subgraph G′ such that for every pair of vertices u, v ∈ G, we have that dG′ (u, v) ≤ (1 + ε) · dG (u, v), where dX (·, ·) denotes the shortest path distance in X . Throughout the paper, we assume that ε isan arbitrary fixed constant with 0 < ε < 1. In computational geometry, there are many works that consider spanners of point sets, where the graph G is the complete graph over the point set and edge weights correspond to Euclidean distances. Results for such Euclidean spanners of point sets include a variety of (1 + ε)-spanners of size O(n/εd−1) [4,6,15,26,37,48,55] . Fora thorough treatment of spanners for Euclidean point sets, we reference the textbook [50] . Spanners are also well studied in other settings, s

FAQs

What problem does the paper address for disk intersection graphs?

It maintains a (1+ε)-spanner over the disk intersection graph of a dynamic set of disks, while also deriving implications for connectivity queries.

How is the disk set restricted in the spanner construction?

All disks are restricted to have their diameters within a fixed and known range [4, Ψ].

What are the main size and update-time guarantees of the dynamic spanner?

The (1+ε)-spanner has size O(nε−2 log Ψ log(ε−1)). Using persistent data structures, it requires O(ε−2n log4 n log Ψ) space and achieves an expected amortised update time of O((Ψ/ε)^2 log4 n log2 Ψ log2(ε−1)).

Jul 16, 2026

Upload by Lucas Martin