Dynamic Light Spanners in Doubling Metrics

Our proof begin somewhat similarly to Eppstein and Khodabandeh [31]: roughly speaking, we seek to maintain a greedy spanner on top of a dynamic sparse spanner of points $X$ (crucially, this spanner is much more structured than just the greedy spanner on the complete geometric graph on $X$). In Section 3, we first give a new (and arguably much simpler²²2We avoid the bucketing technique in the algorithm of [31] and instead work with all spanner edges at once; we maintain spanner invariants that work in doubling metrics and not just Euclidean metrics (unlike the leapfrog property used in [31]); and finally, we give a simple worst-case bound on the recourse of $O(\log \mathrm{\Phi })$, rather than using a potential function to bound the amortized recourse.) algorithm and analysis that such a spanner can be maintained with bounded recourse. After each insertion/deletion, we identify $O(\log \mathrm{\Phi })$ edges $(u,v)$ of our greedy spanner $L$ which might have to change, to satisfy the greedy spanner invariants: roughly speaking, we examine the distance between $u$ and $v$ in the graph consisting of all of edges of $L$ that are shorter than $(u,v)$³³3Our description here assumes we want to maintain a greedy spanner, but actually we maintain a slightly more robust type of spanner which we call the delayed greedy spanner: we work with distances ${\delta }^{\ast }(u,v)$ rather than , as defined in Section 2.2. We do this to control cascading changes to $L$., and we insert or delete $(u,v)$ to $L$ based on whether . Our key technical contribution (in Section 4) is to show that we can efficiently maintain estimates of even as we insert or delete edges into $L$.

In general graphs, the goal is to maintain, under edge updates, for any integer $k\ge 2$, a spanner with stretch $2k-1$ and $\tilde{O}(n^{1+1/k})$ edges. Assuming the Erdős–Girth conjecture, this trade-off is essentially optimal. The dynamic spanner problem was initiated by Ausiello et al. [7], and has since been studied extensively; see, for example, [8, 17, 27, 10, 34]. However, these works focus primarily on sparsity, and the resulting techniques do not naturally extend to maintaining light spanners. Moreover, due to inherent degree barriers in general graphs, this line of work exclusively considers edge updates. In contrast, in geometric and other structured metric spaces, vertex updates are often the more natural model, since the underlying graph need not be maintained explicitly. This distinction is crucial for light spanners, whose construction and analysis rely fundamentally on geometric structure rather than purely combinatorial sparsification.

Spanners have also been studied extensively in the closely related online model. In this setting, points from a metric space arrive one by one, and at each step, the algorithm is given the subset of points that arrived so far. The goal is to maintain a $t$-spanner at all times. Unlike in the fully dynamic setting, the algorithm is allowed to add edges when a new point arrives, but may never remove previously added edges. In addition, the total number of points $n$ is not known in advance. A number of algorithms and lower bounds have been obtained for this model, which addressed both sparsity and lightness guarantees along with stretch, under online constraints; see, e.g., [11, 15, 2, 3, 9, 40, 46]. These results achieve near-optimal trade-offs in the online regime and highlight the fundamental differences between incremental constructions and fully dynamic settings.

Let $X\subseteq 𝒳$ be a set of points. Assume that the smallest distance between points in $X$ is $1$, and the largest distance is $\mathrm{\Phi }$; for simplicity we assume $\mathrm{\Phi }=2^i$ for some integer $i$. A $\mathrm{\Delta }$-net of $X$ is a set of points $N$ such that every point $x\in X$ is within distance $\mathrm{\Delta }$ of some point in $N$, and any two net points in $N$ are at distance greater than $\mathrm{\Delta }$. A $\mathrm{\Delta }$-net can be constructed greedily. A net hierarchy of $X$ is a hierarchical sequence of nets $(N_0,N_1,\mathrm{\dots },N_{\log \mathrm{\Phi }})$ such that every $N_i$ is a subset of $N_{i-1}$, and $N_i$ is a $2^i$-net of $N_{i-1}$; we take $N_0=X$. Observe that (by a geometric series) every point in $X$ is within distance $2^{i+1}$ of some net point in $N_i$. Moreover, the packing bound of doubling metrics implies that there are not too many points close together in each $\mathrm{\Delta }$-net.

An implicit representation of the net hierarchy $𝒩$ can be maintained using a data structure called the net tree [35, 43, 42]. We will sometimes abuse terminology and call $𝒩$ a net tree.

The net-tree spanner was introduced (under the name “deformable spanner”) by Gao, Guibas, and Nguyen [35]; similar ideas were independently designed by Krauthgamer and Lee [43]. The $\epsilon$-net-tree spanner of $X$ with respect to the net tree $𝒩=(N_0,\mathrm{\dots },N_{\log \mathrm{\Phi }})$ is the graph with vertex set $X$ and with the following edge set: for every scale $i\in [\log \mathrm{\Phi }]$, add an edge between any two vertices $u,v\in N_i$ if $\delta (u,v)\le c\cdot 2^i$, where $c≔4+16{\epsilon }^{-1}$.

For any pair of vertices $(u,v)$, we say the scale of $(u,v)$ is the value $i$ such that $\delta (u,v)\in [2^{i-1},2^i)$. Observe that an edge $(u,v)$ at scale $i$ in an $\epsilon$-net-tree spanner has both endpoints in the $O(\epsilon )\cdot 2^i$-net of the net tree (not the $2^i$-net). The packing bound implies that every vertex in the $\epsilon$-net-tree spanner has degree at most ${\epsilon }^{-O(d)}\cdot \log \mathrm{\Phi }$. In fact, using a charging argument, one can show that the $\epsilon$-net-tree spanner contains at most ${\epsilon }^{-O(d)}\cdot n$ edges: that is, it is sparse. We frequently denote the $\epsilon$-net-tree spanner as $S$.

Gao, Guibas, and Nguyen [35] showed that the net tree spanner can be maintained dynamically. We summarize their guarantee below.

We will make use of Lemma 2.1, but we will have to slightly unwrap the black box – we will need some control on how the net tree $𝒩$ changes after each insertion or deletion. Fortunately, [35] update the net tree $𝒩$ in a simple and structured way. Inserting a point $x$ into $X$ has the following result, described in Figure 2.

Deleting a point $x$ from $X$ is described in Figure 3.

We will not discuss the details of the data structures or algorithms that [35] use to implement these two operations efficiently. We have unwrapped the [35] black box so that we can prove that every insertion/deletion of a point $x$ only changes $𝒩$ “locally” nearby $x$.

When $x$ is inserted into $X$ (according to the pseudocode in Figure 2), the lemma follows trivially from the [35] algorithm description: the only point that could differ between $N_i$ and $N_i^{\mathrm{old}}$ is $x$. We now argue that the lemma holds when $x$ is deleted from $X$ (according to the pseudocode in Figure 3). By construction, the only point that could be removed from $N_i^{\mathrm{old}}$ is $x$; that is, the set $N_i^{\mathrm{old}}\setminus N_i$ is either $\mathrm{\varnothing }$ or $\{x\}$. So it remains to show that every point $y$ in $N_i\setminus N_i^{\mathrm{old}}$ satisfies $\delta (y,x)\le 2^i$. The proof is by induction on $i$. When $i=0$, every point in $\text{DS}.X$ is contained in $N_0^{\mathrm{old}}$, so $N_0\setminus N_0^{\mathrm{old}}=\mathrm{\varnothing }$ and the claim holds trivially. Now consider $i>0$. Consider some point $y\in N_i\setminus N_i^{\mathrm{old}}$. By the algorithm description, the point $y$ satisfies

There are two cases. In the first case, suppose $y\in N_{i-1}^{\mathrm{old}}$. Because $N_i^{\mathrm{old}}$ is a $2^i$-net for $N_{i-1}^{\mathrm{old}}$, we have $\delta (y,N_i^{\mathrm{old}})\le 2^i$. We conclude that $\delta (y,x)\le 2^i$ as desired. In the second case, suppose $y\notin N_{i-1}^{\mathrm{old}}$; thus $y\in N_{i-1}\setminus N_{i-1}^{\mathrm{old}}$, and by induction we have that . $◀$

We need one more guarantee from [35] (see full paper for details).

We maintain a light spanner, denoted $S\subseteq S$ that doesn’t obey the greedy spanner invariants exactly; rather, we define a more robust set of invariants. For any scale $i\in [\log \mathrm{\Phi }]$, we define the set of edges $L[i]\subseteq L$ to be the set of all edges in $L$ with scale strictly less than $i$; that is, every edge in $L[i]$ has length at most $2^{i-1}$. For any edge $(u,v)$ of the $\epsilon$-net-tree spanner at scale $i$, we define ${\delta }^{\ast }(u,v)$$≔{\delta }_{L[i]}(u,v)$; recall that ${\delta }_{L[i]}(\cdot ,\cdot )$ denotes the shortest-path metric in the geometric graph induced by $L[i]$. To construct our light spanner, we maintain a subset of edges $L\subseteq S$ with the following properties:

If $L$ satisfies Invariants 8 and 9, we call $L$ a delayed greedy spanner of $S$ (because there is a delay between the time an edge is added to the spanner and the time it is taken into account when making the next decision). We emphasize that the delayed greedy spanner invariants are different than the greedy spanner invariants for $H$: in our invariants, the choice of adding $(u,v)$ to the spanner depends on $L[i]$ (the set of edges in $L$ with scale strictly smaller than the scale of $(u,v)$), rather than (the set of edges in the greedy spanner $H$ that are strictly shorter than $\delta (u,v)$). Nevertheless, we show that any set of edges $L$ that satisfies Invariants 8 and 9 is a $(1+O(\epsilon ))$-spanner (Lemma 2.2) and has constant lightness (Lemma 2.2).

By Lemma 2.1, the $\epsilon$-net-tree spanner $S$ is a $(1+\epsilon )$-spanner for $(X,\delta )$. Moreover, Invariant 8 implies that $L$ is a $(1+\epsilon )$-spanner for $S$: by triangle inequality it suffices to check that every edge of $S$ is preserved up to $1+\epsilon$ approximation in $L$, and indeed, for every edge $(u,v)\in S$, we have ${\delta }_L(u,v)\le {\delta }^{\ast }(u,v)\le (1+\epsilon )\delta (u,v)\le (1+\epsilon ){\delta }_S(u,v)$. We conclude that $L$ is a spanner for $(X,\delta )$ with stretch ${(1+\epsilon )}^2\le (1+3\epsilon )$. $◀$

We use, as a black box, the fact that the greedy $(1+\frac{\epsilon }{3})$-spanner in a metric space of doubling dimension $d$ has lightness ${\epsilon }^{-O(d)}$ [19]. We consider the shortest-path metric ${\delta }_L$ induced by the edges of $L$; because $(X,\delta )$ has doubling dimension $d$, the stretch bound of Lemma 2.2 together with the definition of doubling dimension implies that the doubling dimension of $(X,{\delta }_L)$ is $O(d)$ (see [33, Observation 7]). Consider building the greedy $(1+\frac{\epsilon }{3})$-spanner $\widehat{L}$ of $L$: that is, we initialize $\widehat{L}\leftarrow \mathrm{\varnothing }$, then iterate over the edges of $L$ from smallest to largest⁶⁶6by triangle inequality, it suffices to examine only the edges of $L$ when building the greedy spanner, rather than all pairs of vertices in $L$, and add an edge $(u,v)\in L$ into the spanner $\widehat{L}$ iff ${\delta }_{\widehat{L}}(u,v)>(1+\frac{\epsilon }{3}){\delta }_L(u,v)$. The greedy spanner $\widehat{L}$ has lightness ${\epsilon }^{-O(d)}$. We now charge every edge of $L$ to an edge of $\widehat{L}$. If an edge $(u,v)\in L$ is added to $\widehat{L}$, then charge $(u,v)$ to itself. Otherwise, suppose $(u,v)\in L$ is not added to $\widehat{L}$. This means that there is a path $P$ between $u$ and $v$ in $\widehat{L}$ (at the instant that $(u,v)$ is considered) with length at most $(1+\frac{\epsilon }{3}){\delta }_L(u,v)$. Because $S$ is a geometric graph, ${\delta }_S(u,v)=\delta (u,v)$; i.e., $P$ has length at most $(1+\frac{\epsilon }{3})\delta (u,v)$. Let $i$ be the scale of $(u,v)$, meaning that $\delta (u,v)\in [2^{i-1},2^i)$. The path $P$ contains some scale-$i$ edge $(u^{\prime },v^{\prime })$ in the greedy spanner $\widehat{L}$: otherwise, if $P$ contained only scale-$j$ edges with , we would have ${\delta }^{\ast }(u,v)\le (1+\frac{\epsilon }{3})\cdot \delta (u,v)$, contradicting Invariant 9. Charge $(u,v)$ to the scale-$i$ edge $(u^{\prime },v^{\prime })$.

We now claim that every edge $(u^{\prime },v^{\prime })$ in $\widehat{L}$ is charged at most ${\epsilon }^{-O(d)}$ times. Indeed, whenever a scale-$i$ edge $(u^{\prime },v^{\prime })$ is charged by a scale-$i$ edge $(u,v)$, we have $\delta (u,u^{\prime })\le (1+\frac{\epsilon }{3})2^i$; this is because, by definition of charging, $u^{\prime }$ lies on a path $u$ and $v$ with length at most $(1+\frac{\epsilon }{3})\delta (u,v)\le (1+\frac{\epsilon }{3})2^i$. The packing bound (Observation 2.1) implies that there are only ${\epsilon }^{-O(d)}$ scale-$i$ edges that could charge $(u^{\prime },v^{\prime })$. Because we only charge scale-$i$ edges in $L$ to scale-$i$ edges in $\widehat{L}$, we conclude that $L$ is at most ${\epsilon }^{-O(d)}$ times heavier than $L$, which is ${\epsilon }^{-O(d)}$ times heavier than the minimum spanning tree on $X$. $◀$

Let ${𝒩}^{\mathrm{old}}$, $S^{\mathrm{old}}$, $L^{\mathrm{old}}$, and $X^{\mathrm{old}}$ denote $\text{DS}.𝒩$, $\text{DS}.S$, $\text{DS}.L$, and $\text{DS}.X$ (respectively) before the insertion process. For brevity, we write $𝒩$, $S$, $L$, and $X$ instead of $\text{DS}.𝒩$, $\text{DS}.S$, $\text{DS}.L$, and $\text{DS}.X$. By Lemma 2.1, the variables $\text{DS}.X$, $\text{DS}.𝒩$ and $\text{DS}.S$ are correctly maintained. Moreover, we have that $L\subseteq S$, because (by description of the algorithm) $S^{\mathrm{old}}\subseteq S$ and (by assumption) $L^{\mathrm{old}}\subseteq S^{\mathrm{old}}$.

It remains to show that that every edge $(u,v)$ in $S$ satisfies Invariants 8 and 9. Suppose that edge $(u,v)$ is at scale $i$ (that is, $\delta (u,v)\in (2^{i-1},2^i]$). Note that the distance ${\delta }^{\ast }(u,v)={\delta }_{L[i]}(u,v)$ depends only on the edges in $L$ with scale strictly less than $i$; thus, it suffices to show that $(u,v)$ satisfies the two invariants at the moment after the for-loop processes scale $i$. If $u,v\in B(x,4\cdot 2^i)$, then $(u,v)$ satisfies the two invariants by description of the algorithm. Now suppose that some endpoint, without loss of generality $u$, is not in $B(x,4\cdot 2^i)$. In this case, $(u,v)$ is in $L$ if and only if $(u,v)$ is in $L^{\mathrm{old}}$. There are two cases:

• $\mathrm{■}$

  Suppose that $\mathbf{(}u\mathbf{,}v\mathbf{)}$ is not in $L$. Thus $(u,v)$ is not in $L^{\mathrm{old}}$. To satisfy Invariant 8, we must show ${\delta }_{L[i]}(u,v)\le (1+\epsilon )\cdot \delta (u,v)$. In fact, we show that either ${\delta }_{L[i]}(u,v)\le {\delta }_{L^{\mathrm{old}}[i]}(u,v)$ or ${\delta }_{L^{\mathrm{old}}[i]}(u,v)>2\delta (u,v)$; see Figure 4. This suffices, as $L^{\mathrm{old}}$ satisfies Invariant 8: we conclude that ${\delta }_{L[i]}(u,v)\le {\delta }_{L^{\mathrm{old}}[i]}(u,v)\le (1+\epsilon )\delta (u,v)$ as desired. Consider a shortest path $P$ in $L^{\mathrm{old}}[i]$ between $u$ and $v$. The description of the algorithm implies that the only edges that that change between $L[i]$ and $L^{\mathrm{old}}[i]$ are in the ball $B(x,4\cdot 2^{i-1})$. Because we assumed $\delta (u,x)>4\cdot 2^i$, triangle inequality implies that endpoints of any edge $(u^{\prime },v^{\prime })$ in $L^{\mathrm{old}}[i]\setminus L[i]$ are far from $u$: specifically, $\delta (u,u^{\prime })\ge 4\cdot 2^i-4\cdot 2^{i-1}=2\cdot 2^i$, and so ${\delta }_{L^{\mathrm{old}}}(u,u^{\prime })\ge 2\cdot 2^i$. If $P$ has length $\ge 2\cdot 2^i$ then we are done; otherwise, $P$ does not include any edges in $L^{\mathrm{old}}[i]\setminus L[i]$, and so $P$ is also a path in $L[i]$ as desired.

• $\mathrm{■}$

  Suppose $\mathbf{(}u\mathbf{,}v\mathbf{)}$ is in $L$. Thus $(u,v)$ is in $L^{\mathrm{old}}$. To satisfy Invariant 9, we must show that ${\delta }_{L[i]}(u,v)>(1+\frac{\epsilon }{3})\cdot \delta (u,v)$. We claim that either ${\delta }_{L[i]}(u,v)\ge {\delta }_{L^{\mathrm{old}}[i]}(u,v)$, or ${\delta }_{L[i]}(u,v)\ge 2\delta (u,v)$. This suffices to prove the claim, because $L^{\mathrm{old}}$ satisfies Invariant 9 and so ${\delta }_{L^{\mathrm{old}}[i]}(u,v)>(1+\frac{\epsilon }{3})\delta (u,v)$; thus, in either case, ${\delta }_{L[i]}(u,v)>(1+\frac{\epsilon }{3})\delta (u,v)$. Let $P$ be a shortest path between $u$ and $v$ in $L[i]$. If ${\delta }_{L[i]}(u,v)\ge {\delta }_{L^{\mathrm{old}}[i]}(u,v)$ then we are done. Otherwise, if , then $P$ must contain some edge of $L[i]$ that is not in $L^{\mathrm{old}}[i]$. But the description of the algorithm implies that any such edge has endpoints in $B(x,4\cdot 2^{i-1})$. By triangle inequality and our assumption that $\delta (u,x)\ge 4\cdot 2^i$, we have $\delta (u,u^{\prime })\ge 2\cdot 2^i$, and so $P$ has length at least $2\cdot 2^i$ as desired.

$◀$

We remark that the Insert procedure has bounded recourse: at most ${\epsilon }^{-O(d)}\log \mathrm{\Phi }$ edges change in the spanner $L$. This is because, for every scale $i\in \lceil \log \mathrm{\Phi }\rceil$, there are at most ${\epsilon }^{-O(d)}$ scale-$i$ edges in the $\epsilon$-net-tree spanner in $B(x,4\cdot 2^i)$, by definition of net-tree spanner and packing bound (Observation 2.1).