Dynamic Light Spanners in Doubling Metrics
2026-03-24 • Computational Geometry
Computational GeometryData Structures and Algorithms
AI summaryⓘ
The authors study a way to keep a network connecting points so that the paths between points are almost as short as the direct distance. Their goal is to update this network quickly when points are added or removed, in spaces where points are not too complicatedly spread out. They manage to keep the network light, meaning its total connection length stays close to the smallest possible, and they can update it efficiently. Before this work, there was no known fast method to do this even in simple low-dimensional spaces.
t-spannermetric spacedoubling dimensiondynamic data structureminimum spanning treeaspect ratiograph spannerpoint setupdate time
Authors
Sujoy Bhore, Jonathan Conroy, Arnold Filtser
Abstract
A $t$-spanner of a point set $X$ in a metric space $(\mathcal{X}, δ)$ is a graph $G$ with vertex set $P$ such that, for any pair of points $u,v \in X$, the distance between $u$ and $v$ in $G$ is at most $t$ times $δ(u,v)$. We study the problem of maintaining a spanner for a dynamic point set $X$ -- that is, when $X$ undergoes a sequence of insertions and deletions -- in a metric space of constant doubling dimension. For any constant $\varepsilon>0$, we maintain a $(1+\varepsilon)$-spanner of $P$ whose total weight remains within a constant factor of the weight of the minimum spanning tree of $X$. Each update (insertion or deletion) can be performed in $\operatorname{poly}(\log Φ)$ time, where $Φ$ denotes the aspect ratio of $X$. Prior to our work, no efficient dynamic algorithm for maintaining a light-weight spanner was known even for point sets in low-dimensional Euclidean space.